Facets of the Knapsack Polytope From Minimal Covers
From MaRDI portal
Publication:4166575
DOI10.1137/0134010zbMath0385.90083OpenAlexW2041989601MaRDI QIDQ4166575
Publication date: 1978
Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0134010
Integer programming (90C10) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Polytopes and polyhedra (52Bxx)
Related Items
Implicit cover inequalities, Partial cover and complete cover inequalities, Knapsack polytopes: a survey, On the complexity of sequentially lifting cover inequalities for the knapsack polytope, On the mixing set with a knapsack constraint, Lifted cover facets of the 0-1 knapsack polytope with GUB constraints, An exact algorithm for the reliability redundancy allocation problem, Separation algorithms for 0-1 knapsack polytopes, Facets of the knapsack polytope derived from disjoint and overlapping index configurations, Theoretical challenges towards cutting-plane selection, On optimizing over lift-and-project closures, On facets of knapsack equality polytopes, On the complexity of separation from the knapsack polytope, Lifting the knapsack cover inequalities for the knapsack polytope, A generalization of antiwebs to independence systems and their canonical facets, On the facial structure of the set covering polytope, On cutting-plane proofs in combinatorial optimization, Facets and lifting procedures for the set covering polytope, \(O(n \log n)\) procedures for tightening cover inequalities, Chance-Constrained Binary Packing Problems, A cut-and-solve based algorithm for the single-source capacitated facility location problem, Cover by disjoint cliques cuts for the knapsack problem with conflicting items, A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems, Sequence independent lifting of cover inequalities, Sequence independent lifting for mixed knapsack problems with GUB constraints, New classes of facets for complementarity knapsack problems, The constrained-routing and spectrum assignment problem: valid inequalities and branch-and-cut algorithm, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, The generalized assignment problem: Valid inequalities and facets, Foundation-penalty cuts for mixed-integer programs., Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing, Facet defining inequalities for the dichotomous knapsack problem, On a generalization of the master cyclic group polyhedron, 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, An improved cut-and-solve algorithm for the single-source capacitated facility location problem, Lift-and-Project Cuts for Mixed Integer Convex Programs, 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, Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem, Supermodular covering knapsack polytope, On tightening cover induced inequalities, The complexity of lifted inequalities for the knapsack problem, Compressor scheduling in oil fields. Piecewise-linear formulation, valid inequalities, and computational analysis, A cutting plane approach for integrated planning and scheduling, Polyhedral results for the precedence-constrained knapsack problem, Cutting planes in integer and mixed integer programming, On the exact separation of mixed integer knapsack cuts, A hybrid algorithm for the generalized assignment problem, Lifting the facets of zero–one polytopes, A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem, A polyhedral study on 0-1 knapsack problems with set packing constraints, SCIP: solving constraint integer programs, Optimization algorithms for the disjunctively constrained knapsack problem, Lifting convex inequalities for bipartite bilinear programs, On lifted cover inequalities: a new lifting procedure with unusual properties, Lifting convex inequalities for bipartite bilinear programs, An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., The submodular knapsack polytope, Parametric convex quadratic relaxation of the quadratic knapsack problem, The incremental connected facility location problem, Solving the generalised assignment problem using polyhedral results, Strong bounds for resource constrained project scheduling: preprocessing and cutting planes, On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0-1 knapsack constraint, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Cover and pack inequalities for (mixed) integer programming, A conditional logic approach for strengthening mixed 0-1 linear programs, Integer-programming software systems
