A Procedure for Generating the Convex Hull of a 0-1 Programming Polytope with Positive Coefficients.

Abstract

We present a procedure which generates all the facets of a 0-1 programming polytope P with positive coefficients in a finite number of steps. The procedure is based upon the relationship between facets of P and facets of the knapsack polytopes corresponding to certain nonnegative combinations of inequalities implied by P. Finiteness of the procedure is proven by examining the relationship of the valid inequalities generated during each step of the procedure in connection with a result due to Chvatal. In addition to exploring the properties of inequalities generated by the procedure, several properties of the classes of valid inequalities for the knapsack polytope defined in Balas and Balas and Jeroslow are presented. In particular, the set of canonical inequalities is shown to belong to Chvatal's elementary closure. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1980
Accession Number
ADA097762

Entities

People

  • Joseph B. Mazzola

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Coefficients
  • Computer Programming
  • Evolutionary Algorithms
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • New York
  • North Carolina
  • Numbers
  • Optimization
  • Real Numbers
  • Schools
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research