Easily Computable Facets of the Knapsack Polytope
From MaRDI portal
Publication:3032082
DOI10.1287/moor.14.4.760zbMath0689.90057OpenAlexW2137021253MaRDI QIDQ3032082
Publication date: 1989
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/dda954957ede2d3b15aa33ca47cf1a773647891d
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27) Dynamic programming (90C39) Polytopes and polyhedra (52Bxx)
Related Items
Implicit cover inequalities, Knapsack polytopes: a survey, On the complexity of sequentially lifting cover inequalities for the knapsack polytope, Cover inequalities for robust knapsack sets-Application to the robust bandwidth packing problem, Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem, Lifted cover facets of the 0-1 knapsack polytope with GUB constraints, Separation algorithms for 0-1 knapsack polytopes, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, On facets of knapsack equality polytopes, Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning, Lifting the knapsack cover inequalities for the knapsack polytope, \(O(n \log n)\) procedures for tightening cover inequalities, Chance-Constrained Binary Packing Problems, A polyhedral study on chance constrained program with random right-hand side, Lifting for the integer knapsack cover polyhedron, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, Lifting of probabilistic cover inequalities, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, Approximate and exact merging of knapsack constraints with cover inequalities, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes, Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities, Adjacency of the 0-1 knapsack problem, The Minkowski sum of simplices in 3-dimensional space. An analytical description, On tightening cover induced inequalities, The complexity of lifted inequalities for the knapsack problem, The aggregate capacity of virtual resources – linear models, Polyhedral results for the precedence-constrained knapsack problem, A polyhedral study on 0-1 knapsack problems with set packing constraints, Optimization algorithms for the disjunctively constrained knapsack problem, On lifted cover inequalities: a new lifting procedure with unusual properties, Efficient reformulation for 0-1 programs -- methods and computational results, An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., Parametric convex quadratic relaxation of the quadratic knapsack problem, A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming, Order selection on a single machine with high set-up costs, Cover and pack inequalities for (mixed) integer programming
