Accession Number:

AD0753472

Title:

Constraint Classification on the Unit Hypercube

Descriptive Note:

Research rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

• Bowman, V. J.

Report Date:

1972-07-01

Pagination or Media Count:

29.0

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.

Descriptors:

• *MATHEMATICAL PROGRAMMING
• ALGORITHMS
• CLASSIFICATION
• VECTOR SPACES
• SET THEORY
• THEOREMS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE