(1,k)-configurations and facets for packing problems
From MaRDI portal
Publication:3869083
DOI10.1007/BF01588301zbMath0431.90050MaRDI QIDQ3869083
Publication date: 1980
Published in: Mathematical Programming (Search for Journal in Brave)
integer programmingintegral polyhedralinear inequalitiesfacetscombinatorial inequalitypacking problemsknapsack polytope(1,k)-configurationsFulkerson's max-max inequalityintegrality result
Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Polytopes and polyhedra (52Bxx)
Related Items
Valid inequalities for mixed 0-1 programs, Knapsack polytopes: a survey, Separation algorithms for 0-1 knapsack polytopes, Facets of the knapsack polytope derived from disjoint and overlapping index configurations, On the complexity of separation from the knapsack polytope, Facets and lifting procedures for the set covering polytope, Sequence independent lifting for mixed knapsack problems with GUB constraints, New classes of facets for complementarity knapsack problems, Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, Convex hulls of superincreasing knapsacks and lexicographic orderings, The generalized assignment problem: Valid inequalities and facets, Facet defining inequalities for the dichotomous knapsack problem, On facet-inducing inequalities for combinatorial polytopes, A note on the knapsack problem with special ordered sets, The multidimensional 0-1 knapsack problem: an overview., The precedence constrained knapsack problem: separating maximally violated inequalities, Classical cuts for mixed-integer programming and branch-and-cut, A characterization of knapsacks with the max-flow--min-cut property, A new extended formulation of the generalized assignment problem and some associated valid inequalities, Discrete relaxations of combinatorial programs, A polyhedral study on 0-1 knapsack problems with set packing constraints, A new extended formulation with valid inequalities for the capacitated concentrator location problem, Polyhedral techniques in combinatorial optimization I: Theory, Multi-cover inequalities for totally-ordered multiple knapsack sets, Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope, Valid inequalities, cutting planes and integrality of the knapsack polytope, The submodular knapsack polytope, Some integer programs arising in the design of main frame computers, The maximum clique problem, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Cover and pack inequalities for (mixed) integer programming
Cites Work
- Technical Note—A Note on Zero-One Programming
- Faces for a linear inequality in 0–1 variables
- Facet of regular 0–1 polytopes
- Facets of the knapsack polytope
- Properties of vertex packing and independence system polyhedra
- On the facial structure of set packing polyhedra
- Blocking and anti-blocking pairs of polyhedra
- Unnamed Item
