Abstract
A new class of facets for knapsack polytopes is obtained. This class of inequalities is shown to define a polytope with zero–one vertices only. A combinatorial inequality is obtained from Fulkerson's max—max inequality.
This is a preview of subscription content, log in via an institution to check access.
References
E. Balas, “Facets of the knapsack polytope”,Mathematical Programming 8 (1975) 146–164.
D.R. Fulkerson, “Blocking and anti-blocking pairs of polyhedra”,Mathematical Programming 1 (1971) 168–194.
P.L. Hammer, E.L. Johnson and U.N. Peled, “Facets of regular 0–1 polytopes”,Mathematical Programming 8 (1975) 179–206.
G.L. Nemhauser and L.E. Trotter, Jr., “Properties of vertex packing and independence system polyhedra”,Mathematical Programming 6 (1974) 48–61.
M.W. Padberg, “On the facial structure of set packing polyhedra”,Mathematical Programming 5 (1973) 199–216.
M.W. Padberg, “A note on zero–one programming”,Operations Research 23 (1975) 833–837.
U.N. Peled, “Properties of facets of binary polytopes”, Ph.D. Thesis, Dept. of Combinatorics and Optimization, University of Waterloo (1976).
L.A. Wolsey, “Faces for a linear inequality in 0–1 variables”,Mathematical Programming 8 (1975) 165–178.
E. Zemel, “On the facial structure of zero–one polytopes”, Ph.D. Thesis, GSIA, Carnegie-Mellon University (1976).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Padberg, M.W. (1,k)-configurations and facets for packing problems. Mathematical Programming 18, 94–99 (1980). https://doi.org/10.1007/BF01588301
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588301