Constraint Classification on the Unit Hypercube
Abstract
The paper shows that there is a finite set of equivalence classes for constraints in the 0-1 programming problem. These equivalence classes have the property that exactly the same set of solutions are feasible for all constraints in the equivalence class. It is shown that these classes are determined by the relationship of the constraint to the dual of the hypercube. A function that indicates feasibility of 0-1 points is defined and is shown to be monotone over a vector partial ordering associated with the constraint and paired vertices of the hypercube. This allows for determination of equivalence classes based on identifying where the indicator function changes value. A search algorithm is presented for classifying the constraints and a method is presented for determining a best constraint from the class.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1972
- Accession Number
- AD0753472
Entities
People
- V. J. Bowman
Organizations
- Carnegie Mellon University