On the \(0/1\) knapsack polytope
From MaRDI portal
Publication:1373759
zbMath0891.90130MaRDI QIDQ1373759
Publication date: 1997
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
separationfacetscomplete description\(0/1\) knapsack polytopepseudo polynomial timeweight inequalities
Related Items (40)
Knapsack polytopes: a survey ⋮ Separation algorithms for 0-1 knapsack polytopes ⋮ Theoretical challenges towards cutting-plane selection ⋮ LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison ⋮ On facets of knapsack equality polytopes ⋮ On the complexity of separation from the knapsack polytope ⋮ Lifting the knapsack cover inequalities for the knapsack polytope ⋮ The quadratic knapsack problem -- a survey ⋮ A cut-and-solve based algorithm for the single-source capacitated facility location problem ⋮ A cut-and-branch algorithm for the quadratic knapsack problem ⋮ A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem ⋮ Lifting for the integer knapsack cover polyhedron ⋮ 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 ⋮ On the transportation problem with market choice ⋮ An improved cut-and-solve algorithm for the single-source capacitated facility location problem ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Quadratic knapsack relaxations using cutting planes and semidefinite programming ⋮ Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes ⋮ Generalized coefficient strengthening cuts for mixed integer programming ⋮ Polyhedral properties for the intersection of two knapsacks ⋮ Recoverable robust knapsacks: the discrete scenario case ⋮ Progress in computational mixed integer programming -- a look back from the other side of the tipping point ⋮ Cutting planes in integer and mixed integer programming ⋮ The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs ⋮ Where are the hard knapsack problems? ⋮ Discrete relaxations of combinatorial programs ⋮ A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem ⋮ Aggregation-based cutting-planes for packing and covering integer programs ⋮ A polyhedral study on 0-1 knapsack problems with set packing constraints ⋮ Optimization algorithms for the disjunctively constrained knapsack problem ⋮ New valid inequalities for the fixed-charge and single-node flow polytopes ⋮ An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope. ⋮ Multi-cover inequalities for totally-ordered multiple knapsack sets ⋮ Face dimensions of general-purpose cutting planes for mixed-integer linear programs ⋮ Cutting planes for integer programs with general integer variables ⋮ On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0-1 knapsack constraint ⋮ Cover and pack inequalities for (mixed) integer programming
This page was built for publication: On the \(0/1\) knapsack polytope
