Lower bounds on the sizes of integer programs without additional variables

DOI10.1007/s10107-014-0855-0zbMath1338.52013arXiv1311.3255OpenAlexW2115718900MaRDI QIDQ896270

Volker Kaibel, Stefan Weltge

Publication date: 9 December 2015

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.3255

zbMATH Keywords

integer programmingauxiliary variablesrelaxationstsp

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Complexity of linear relaxations in integer programming ⋮ Efficient MIP techniques for computing the relaxation complexity ⋮ Lower bounds on the sizes of integer programs without additional variables ⋮ The role of rationality in integer-programming relaxations ⋮ Computational aspects of relaxation complexity: possibilities and limitations ⋮ Sublinear Bounds for a Quantitative Doignon--Bell--Scarf Theorem ⋮ Strong IP formulations need large coefficients ⋮ Sparsity of integer formulations for binary programs ⋮ Balas formulation for the union of polytopes is optimal ⋮ Computational aspects of relaxation complexity

Cites Work

• Unnamed Item
• On the extension complexity of combinatorial polytopes
• Lower bounds on the sizes of integer programs without additional variables
• Using separation algorithms to generate mixed integer model reformulations
• Expressing combinatorial optimization problems by linear programs
• On defining sets of vertices of the hypercube by linear inequalities
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A note on the extension complexity of the knapsack polytope
• On a Binary-Encoded ILP Coloring Formulation
• Integer Programming Formulation of Traveling Salesman Problems
• The Matching Polytope has Exponential Extension Complexity
• Computational Complexity
• Linear vs. semidefinite extended formulations
• An Inequality

This page was built for publication: Lower bounds on the sizes of integer programs without additional variables