Accession Number:

ADA093963

Title:

Valid Inequalities for 0-1 Programming Polytopes.

Descriptive Note:

Management sciences research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1980-11-01

Pagination or Media Count:

24.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE