Easily Computable Facets of the Knapsack Polytope

DOI10.1287/MOOR.14.4.760zbMATH Open0689.90057OpenAlexW2137021253MaRDI QIDQ3032082FDOQ3032082

Authors: Eitan Zemel 

Publication date: 1989

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/dda954957ede2d3b15aa33ca47cf1a773647891d

Recommendations

• On the facets of the mixed-integer knapsack polyhedron
• An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.
• On facets of knapsack equality polytopes
• Facets of the Complementarity Knapsack Polytope
• Knapsack polytopes: a survey
• On the \(0/1\) knapsack polytope
• A note on the extension complexity of the knapsack polytope
• On the multiple integer knapsack polyhedra
• On the complexity of separation from the knapsack polytope
• scientific article; zbMATH DE number 1187156

zbMATH Keywords

computational complexityfacetsliftingvalid inequalitiesknapsack polytope

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Integer programming (90C10) Polytopes and polyhedra (52Bxx) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Cited In (47)

• Polyhedral results for the precedence-constrained knapsack problem
• Lifting of probabilistic cover inequalities
• Lifting the knapsack cover inequalities for the knapsack polytope
• Implicit cover inequalities
• Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
• Lifting for the integer knapsack cover polyhedron
• The complexity of lifted inequalities for the knapsack problem
• Technical Note—Some Very Easy Knapsack/Partition Problems
• A Characterization of Lifted-Cover Facets of Knapsack Polytope with GUB Constraints
• An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.
• A polyhedral study on chance constrained program with random right-hand side
• Knapsack polytopes: a survey
• On tightening cover induced inequalities
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
• Order selection on a single machine with high set-up costs
• \(O(n \log n)\) procedures for tightening cover inequalities
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms
• On the facets of the mixed-integer knapsack polyhedron
• A concise characterization of strong knapsack facets
• On the complexity of sequentially lifting cover inequalities for the knapsack polytope
• Efficient reformulation for 0-1 programs -- methods and computational results
• The Minkowski sum of simplices in 3-dimensional space. An analytical description
• On lifted cover inequalities: a new lifting procedure with unusual properties
• Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities
• Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
• Parametric convex quadratic relaxation of the quadratic knapsack problem
• Approximate and exact merging of knapsack constraints with cover inequalities
• A polyhedral study on 0-1 knapsack problems with set packing constraints
• Cover and pack inequalities for (mixed) integer programming
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem
• Separation algorithms for 0-1 knapsack polytopes
• Optimization algorithms for the disjunctively constrained knapsack problem
• The aggregate capacity of virtual resources – linear models
• Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
• A new sequential lifting of robust cover inequalities
• A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming
• On facets of knapsack equality polytopes
• Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
• Two-set inequalities for the binary knapsack polyhedra
• Facets of the Complementarity Knapsack Polytope
• Cover inequalities for robust knapsack sets -- application to the robust bandwidth packing problem
• Chance-Constrained Binary Packing Problems
• Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning
• Adjacency of the 0-1 knapsack problem
• The worst case analysis of strong knapsack facets

This page was built for publication: Easily Computable Facets of the Knapsack Polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3032082)