Testing additive integrality gaps

DOI10.1007/S10107-012-0518-YMaRDI QIDQ378120zbMATH OpenOpenAlexFDO

Authors Friedrich Eisenbrand, Nicolai Hähnle, Dömötör Pálvölgyi, Gennady Shmonin

Publication date 11 November 2013

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-012-0518-y

zbMATH Keywords

NP-hardinteger rounding property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06)

Recommendations

• Testing additive integrality gaps
• Proving integrality gaps without knowing the linear program
• Integrality gaps of integer knapsack problems
• Computing the integer programming gap
• Test sets for integer programs

Cites work

• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A polynomial-time test for total dual integrality in fixed dimension
• Colorings of k-balanced matrices and integer decomposition property of related polyhedra
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of the Frobenius problem
• Computing the integer programming gap
• Decomposition of regular matroids
• Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
• Integer Programming with a Fixed Number of Variables
• Integer Rounding for Polymatroid and Branching Optimization Problems
• Integral Extreme Points
• Lattice translates of a polytope and the Frobenius problem
• Node-Packing Problems with Integer Rounding Properties
• On the complexity of integer programming
• On total dual integrality
• Parametric integer programming in fixed dimension
• Recognizing conic TDI systems is hard
• The complexity of recognizing linear systems with certain integrality properties

Cited in

(6)

• Error bounds for mixed integer linear optimization problems
• Testing additive integrality gaps
• A note on the integrality gap of an ILP formulation for the periodic maintenance problem
• The gap function: evaluating integer programming models over multiple right-hand sides
• Distances to lattice points in knapsack polyhedra
• On the lattice programming gap of the group problems

This page was built for publication: Testing additive integrality gaps

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