Polynomial size IP formulations of knapsack may require exponentially large coefficients

DOI10.1016/j.orl.2020.07.013zbMath1479.90136OpenAlexW3046357074MaRDI QIDQ2661530

Christopher Hojny

Publication date: 7 April 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2020.07.013

zbMATH Keywords

knapsack polytopeinteger programming formulationsize of coefficients

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Complexity of linear relaxations in integer programming ⋮ Efficient MIP techniques for computing the relaxation complexity ⋮ Computational aspects of relaxation complexity: possibilities and limitations ⋮ Computational aspects of relaxation complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On interval-subgradient and no-good cuts
• Knapsack polytopes: a survey
• Geometric algorithms and combinatorial optimization
• An exact algorithm for the maximum stable set problem
• The rank facets of the stable set polytope for claw-free graphs
• Polytopes associated with symmetry handling
• Independent Set in P₅-Free Graphs in Polynomial Time
• Linear vs. semidefinite extended formulations
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
• Canonical Cuts on the Unit Hypercube