The role of rationality in integer-programming relaxations
DOI10.1007/s10107-023-01994-warXiv2206.12253OpenAlexW4384200885MaRDI QIDQ6126664
Marco Di Summa, Manuel Aprile, Gennadiy Averkov, Christopher Hojny
Publication date: 9 April 2024
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2206.12253
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quantifier elimination, model completeness, and related topics (03C10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- 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
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- Extended formulations for matroid polytopes through randomized protocols
- Computational aspects of relaxation complexity: possibilities and limitations
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Branched Polyhedral Systems
- The Matching Polytope has Exponential Extension Complexity
- Regular Matroids Have Polynomial Extension Complexity
- Nonnegative Matrix Factorization Requires Irrationality
- Extended formulations from communication protocols in output-efficient time
- Extended formulations in combinatorial optimization
- Efficient MIP techniques for computing the relaxation complexity
This page was built for publication: The role of rationality in integer-programming relaxations
