Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation

DOI10.1016/0166-218X(95)90600-KzbMath0835.90052OpenAlexW2009082978MaRDI QIDQ1804882

Yves Pochet, Laurence A. Wolsey

Publication date: 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(95)90600-k

zbMATH Keywords

network designseparationknapsackconvex hulls

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10)

Related Items

Knapsack polytopes: a survey, A polynomial-time algorithm for knapsack with divisible item sizes, Unsplittable non-additive capacitated network design using set functions polyhedra, Discretized formulations for capacitated location problems with modular distribution costs, Lifting two-integer knapsack inequalities, On variations of the subset sum problem, A new upper bound for the multiple knapsack problem, Motion planning with pulley, rope, and baskets, The Mixing Set with Divisible Capacities, Lifting for the integer knapsack cover polyhedron, On \(n\)-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets, Convex hulls of superincreasing knapsacks and lexicographic orderings, Compact formulations as a union of polyhedra, The mixing-MIR set with divisible capacities, Facets for single module and multi-module capacitated lot-sizing problems without backlogging, Manufacturer's mixed pallet design problem, Cutting planes in integer and mixed integer programming, Formulations and valid inequalities for the heterogeneous vehicle routing problem, The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs, A well-solvable special case of the bounded knapsack problem, A polynomial algorithm for the multiple knapsack problem with divisible item sizes, Cutting planes for integer programs with general integer variables, Optimal placement of add/drop multiplexers: Static and dynamic models, Cover and pack inequalities for (mixed) integer programming, Continuous knapsack sets with divisible capacities

Cites Work

• Some polyhedra related to combinatorial problems
• The cutting stock problem and integer rounding
• When the Greedy Solution Solves a Class of Knapsack Problems
• Lot-Sizing with Constant Batches: Formulation and Valid Inequalities