Knapsack polytopes: a survey
From MaRDI portal
Recommendations
Cites work
- (1,k)-configuration facets for the generalized assignment problem
- (1,k)-configurations and facets for packing problems
- A characterization of knapsacks with the max-flow--min-cut property
- A characterization of threshold matroids
- A computational study of exact knapsack separation for the generalized assignment problem
- A cutting plane method for knapsack polytope
- A generalization of antiwebs to independence systems and their canonical facets
- A note on the extension complexity of the knapsack polytope
- A note on the knapsack problem with special ordered sets
- A polyhedral study of the cardinality constrained knapsack problem
- A polyhedral study of the mixed integer cut
- A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
- A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
- A pseudopolynomial network flow formulation for exact knapsack separation
- A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
- Adjacency of the 0-1 knapsack problem
- Aggregation and Mixed Integer Rounding to Solve MIPs
- An implementation of exact knapsack separation
- Approximate counting by dynamic programming
- Approximate extended formulations
- Approximate formulations for 0-1 knapsack sets
- Coefficient reduction for inequalities in 0–1 variables
- Combinatorial optimization. Theory and algorithms.
- Complete description of a class of knapsack polytopes.
- Computational study of a family of mixed-integer quadratic programming problems
- Computational testing of a separation procedure for the knapsack set with a single continuous variable
- Computing low-capacity 0–1 knapsack polytopes
- Convex hulls of superincreasing knapsacks and lexicographic orderings
- Cover and pack inequalities for (mixed) integer programming
- Cutting planes for integer programs with general integer variables
- Cutting planes for mixed-integer knapsack polyhedra
- Cutting planes in integer and mixed integer programming
- Cyclic group and knapsack facets
- Describing orbitopes by linear inequalities and projection based tools.
- Discrete-variable extremum problems
- Easily Computable Facets of the Knapsack Polytope
- Extended formulations in combinatorial optimization
- Faces for a linear inequality in 0–1 variables
- Facet of regular 0–1 polytopes
- Facets of the independent set polytope
- Facets of the knapsack polytope
- Facets of the knapsack polytope derived from disjoint and overlapping index configurations
- Facets of the Knapsack Polytope From Minimal Covers
- Fenchel Cutting Planes for Integer Programs
- Generating cuts from surrogate constraint analysis for zero-one and multiple choice programming
- Generating Fenchel Cutting Planes for Knapsack Polyhedra
- Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities
- Hilbert Bases and the Facets of Special Knapsack Polytopes
- scientific article; zbMATH DE number 3874956 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1187156 (Why is no real title available?)
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 40470 (Why is no real title available?)
- scientific article; zbMATH DE number 3566549 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 1538123 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- scientific article; zbMATH DE number 833409 (Why is no real title available?)
- scientific article; zbMATH DE number 847586 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
- Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation
- Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
- Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
- Lifted flow cover inequalities for mixed 0-1 integer programs
- Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms
- Lifted inequalities for 0-1 mixed integer programming: superlinear lifting
- Lifting cover inequalities for the precedence-constrained knapsack problem
- Lifting the facets of zero–one polytopes
- Lifting valid inequalities for the precedence constrained knapsack problem
- Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
- Matroidal relaxations for 0-1 knapsack problems
- Matroids and the greedy algorithm
- Merging valid inequalities over the multiple knapsack polyhedron
- Mixed integer programming: analyzing 12 years of progress
- Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix
- On facets of knapsack equality polytopes
- On lifted cover inequalities: a new lifting procedure with unusual properties
- On separating cover inequalities for the multidimensional knapsack problem
- On the \(0/1\) knapsack polytope
- On the exact separation of mixed integer knapsack cuts
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- On the facets of the mixed-integer knapsack polyhedron
- On the Facial Structure of Independence System Polyhedra
- On the facial structure of the set covering polytope
- On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
- On tightening cover induced inequalities
- Polyhedral Characterization of Discrete Dynamic Programming
- Polyhedral properties for the intersection of two knapsacks
- Polyhedral results for the precedence-constrained knapsack problem
- polymake: a framework for analyzing convex polytopes
- Polytopes associated with symmetry handling
- Revlex-initial 0/1-polytopes
- Second-order cover inequalities
- Separation algorithms for 0-1 knapsack polytopes
- Sequence independent lifting in mixed integer programming
- Sequential and Simultaneous Liftings of Minimal Cover Inequalities for Generalized Upper Bound Constrained Knapsack Polytopes
- Simple lifted cover inequalities and hard knapsack problems
- Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
- Solving Large-Scale Zero-One Linear Programming Problems
- Solving Multiple Knapsack Problems by Cutting Planes
- Symmetries in binary programs. A polyhedral perspective
- Technical Note—A Note on Zero-One Programming
- Technical Note—Facets and Strong Valid Inequalities for Integer Programs
- The 0-1 knapsack problem with a single continuous variable
- The complementary class of generalized flow cover inequalities
- The complexity of cover inequality separation
- The complexity of facets (and some facets of complexity)
- The complexity of facets resolved
- The complexity of lifted inequalities for the knapsack problem
- The cutting stock problem and integer rounding
- The generalized assignment problem: Valid inequalities and facets
- The Integer Knapsack Cover Polyhedron
- The Role of Master Polytopes in the Unit Cube
- The Sequential Knapsack Polytope
- The vertices of the knapsack polytope
- The worst case analysis of strong knapsack facets
- Transformation of integer programs to knapsack problems
- Valid Inequalities and Superadditivity for 0–1 Integer Programs
- Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
- Valid inequalities for mixed 0-1 programs
- Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem
Cited in
(30)- 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
- On the facets of the mixed-integer knapsack polyhedron
- 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
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- On integer polytopes with few nonzero vertices
- Polyhedral properties for the intersection of two knapsacks
- Optimizing some constructions with bars: new geometric knapsack problems
- Lifting the knapsack cover inequalities for the knapsack polytope
- Polynomial size IP formulations of knapsack may require exponentially large coefficients
- Knapsack Cover Subject to a Matroid Constraint
- Easily Computable Facets of the Knapsack Polytope
- Valid inequalities, cutting planes and integrality of the knapsack polytope
- The Integer Knapsack Cover Polyhedron
- scientific article; zbMATH DE number 1187156 (Why is no real title available?)
- scientific article; zbMATH DE number 729909 (Why is no real title available?)
- Hilbert Bases and the Facets of Special Knapsack Polytopes
- On the multiple integer knapsack polyhedra
- Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
- Lifting for the integer knapsack cover polyhedron
- New classes of facets for complementarity knapsack problems
- New classes of facets for complementarity knapsack problems
- Two-set inequalities for the binary knapsack polyhedra
- Geometric Knapsack problems
- Lifting cover inequalities for the robust knapsack problem
- Computational aspects of lifted cover inequalities for knapsacks with few different weights
This page was built for publication: Knapsack polytopes: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827125)
