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

DOI10.1016/0166-218X(95)90600-KMaRDI QIDQ1804882zbMATH OpenOpenAlexFDO

Authors 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

convex hullsnetwork designseparationknapsack

Mathematics Subject Classification ID

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

Recommendations

• A pseudopolynomial network flow formulation for exact knapsack separation
• The Integer Knapsack Cover Polyhedron
• Continuous knapsack sets with divisible capacities
• A characterization of knapsacks with the max-flow--min-cut property

Cites work

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

Cited in

(27)

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

This page was built for publication: Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1804882)