Knapsack polytopes: a survey
From MaRDI portal
Publication:827125
DOI10.1007/s10479-019-03380-2zbMath1456.90133OpenAlexW2974397306MaRDI QIDQ827125
Publication date: 6 January 2021
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-019-03380-2
liftingcomplete linear descriptionindependence systemsseparation problemknapsack polytopecover inequality
Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items
Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Polynomial size IP formulations of knapsack may require exponentially large coefficients, Lifting for the integer knapsack cover polyhedron, New classes of facets for complementarity knapsack problems, Multi-cover inequalities for totally-ordered multiple knapsack sets, Robust vehicle routing under uncertainty via branch-price-and-cut, On the exact separation of cover inequalities of maximum-depth
Uses Software
Cites Work
- An implementation of exact knapsack separation
- A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
- A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
- The worst case analysis of strong knapsack facets
- On the exact separation of mixed integer knapsack cuts
- Lifting cover inequalities for the precedence-constrained knapsack problem
- Cutting planes in integer and mixed integer programming
- Cover and pack inequalities for (mixed) integer programming
- On separating cover inequalities for the multidimensional knapsack problem
- Convex hulls of superincreasing knapsacks and lexicographic orderings
- The generalized assignment problem: Valid inequalities and facets
- (1,k)-configuration facets for the generalized assignment problem
- Second-order cover inequalities
- Approximate formulations for 0-1 knapsack sets
- 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
- A computational study of exact knapsack separation for the generalized assignment problem
- The vertices of the knapsack polytope
- The complexity of facets (and some facets of complexity)
- Valid inequalities for mixed 0-1 programs
- Facets of the knapsack polytope derived from disjoint and overlapping index configurations
- The complexity of facets resolved
- On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
- A generalization of antiwebs to independence systems and their canonical facets
- On the facial structure of the set covering polytope
- A characterization of threshold matroids
- A note on the knapsack problem with special ordered sets
- Adjacency of the 0-1 knapsack problem
- A characterization of knapsacks with the max-flow--min-cut property
- On tightening cover induced inequalities
- The complexity of lifted inequalities for the knapsack problem
- Polyhedral results for the precedence-constrained knapsack problem
- Cutting planes for integer programs with general integer variables
- Cutting planes for mixed-integer knapsack polyhedra
- The 0-1 knapsack problem with a single continuous variable
- The complexity of cover inequality separation
- Matroidal relaxations for 0-1 knapsack problems
- The complementary class of generalized flow cover inequalities
- Generating cuts from surrogate constraint analysis for zero-one and multiple choice programming
- On facets of knapsack equality polytopes
- On the \(0/1\) knapsack polytope
- Complete description of a class of knapsack polytopes.
- A polyhedral study of the cardinality constrained knapsack problem
- Cyclic group and knapsack facets
- Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms
- Lifted inequalities for 0-1 mixed integer programming: superlinear lifting
- On the facets of the mixed-integer knapsack polyhedron
- Facets of the independent set polytope
- Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
- Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix
- Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation
- Lifting valid inequalities for the precedence constrained knapsack problem
- Computational study of a family of mixed-integer quadratic programming problems
- A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
- Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
- Sequence independent lifting in mixed integer programming
- On lifted cover inequalities: a new lifting procedure with unusual properties
- A cutting plane method for knapsack polytope
- Polytopes associated with symmetry handling
- A note on the extension complexity of the knapsack polytope
- Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
- Polyhedral properties for the intersection of two knapsacks
- Revlex-initial 0/1-polytopes
- Transformation of integer programs to knapsack problems
- Simple lifted cover inequalities and hard knapsack problems
- Approximate extended formulations
- Merging valid inequalities over the multiple knapsack polyhedron
- Separation algorithms for 0-1 knapsack polytopes
- Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
- Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable
- Easily Computable Facets of the Knapsack Polytope
- Polyhedral Characterization of Discrete Dynamic Programming
- The Integer Knapsack Cover Polyhedron
- A Polyhedral Study of the Mixed Integer Cut
- Approximate counting by dynamic programming
- Aggregation and Mixed Integer Rounding to Solve MIPs
- Solving Large-Scale Zero-One Linear Programming Problems
- The cutting stock problem and integer rounding
- On the Facial Structure of Independence System Polyhedra
- Lifting the facets of zero–one polytopes
- (1,k)-configurations and facets for packing problems
- Computing low-capacity 0–1 knapsack polytopes
- A pseudopolynomial network flow formulation for exact knapsack separation
- Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
- Coefficient reduction for inequalities in 0–1 variables
- 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
- Technical Note—Facets and Strong Valid Inequalities for Integer Programs
- The Role of Master Polytopes in the Unit Cube
- Facets of the Knapsack Polytope From Minimal Covers
- Valid Inequalities and Superadditivity for 0–1 Integer Programs
- Generating Fenchel Cutting Planes for Knapsack Polyhedra
- Fenchel Cutting Planes for Integer Programs
- Hilbert Bases and the Facets of Special Knapsack Polytopes
- The Sequential Knapsack Polytope
- Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
- Sequential and Simultaneous Liftings of Minimal Cover Inequalities for Generalized Upper Bound Constrained Knapsack Polytopes
- Solving Multiple Knapsack Problems by Cutting Planes
- Mixed Integer Programming: Analyzing 12 Years of Progress
- Discrete-Variable Extremum Problems
- Matroids and the greedy algorithm
- Combinatorial optimization. Theory and algorithms.
- Extended formulations in combinatorial optimization
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
