Constraint Classification on the Unit Hypercube
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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.
- Operations Research