Valid Inequalities for 0-1 Programming Polytopes.
Abstract
We introduce a family of valid inequalities for 0-1 programming polytopes that are typically not implied by individual problem constraints or by proper subsets of the full constraint set. The computational effort involved in generating such an inequality is linear in the number of variables and in the number of constraints. Several procedures are known in the literature for generating valid inequalities for, or facets of, knapsack polytopes, i.e., 0-1 programming polytopes with a single constraint. Although these inequalities are usually stronger than the corresponding Gomory cuts, since they make use of the binary nature of the variables, their strength is still limited by the fact that they are derived from single constraints. The inequalities introduced here can be viewed as generalizations to the multi-constraint case of the inequalities derived for the knapsack polytope.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1980
- Accession Number
- ADA093963
Entities
People
- Egon Balas
- Joseph B. Mazzola
Organizations
- Carnegie Mellon University