Options
New support bounds and proximity bounds for integer linear programming
Publikationstyp
Conference Paper
Date Issued
2024-02
Sprache
English
First published in
Number in series
14519
Start Page
82
End Page
95
Citation
International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2024)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Springer Cham
ISBN
978-3-031-52112-6
978-3-031-52113-3
Integer linear programming (ILP) is a fundamental research paradigm in algorithms. Many modern algorithms to solve structured ILPs efficiently follow one of two main approaches. The first one is to prove a small upper bound on the support size of the ILP, which is the number of variables taking non-zero values in an optimal solution, and then to only search for ILP solutions of mall support. The second one is to apply an augmentation algorithm using Graver elements to an initial feasible solution obtained from a small proximity bound for the ILP, which is the distance between an optimal solution of the ILP and that of its LP relaxation.
Our first contribution are new lower bounds for the support size of ILPs. Namely, we discover a connection between support sizes and an old number-theoretic conjecture by Erdős on subset-sum distinct sets. Furthermore, we improve the previously best-known lower bounds on the support size of ILPs with m variables and largest coefficient ∆ from Ω(m log(∆)) to Ω(m log(√m∆)). This new lower bound asymptotically matches the best-known upper bounds.
Our second contribution are new bounds on the size of Graver elements and on the proximity for ILPs. We first show nearly tight lower and upper bounds for gmax(A), the maximal size ∥g∥1 of any Graver element g of the Graver basis of the matrix A. Finally, we show that the proximity of any ILP (A, b, c) in standard form with m constraints is bounded by m · gmax(A). Previous works proved such proximity bounds in terms of the number n of variables and gmax(A), however, m can be much smaller than n.
Our first contribution are new lower bounds for the support size of ILPs. Namely, we discover a connection between support sizes and an old number-theoretic conjecture by Erdős on subset-sum distinct sets. Furthermore, we improve the previously best-known lower bounds on the support size of ILPs with m variables and largest coefficient ∆ from Ω(m log(∆)) to Ω(m log(√m∆)). This new lower bound asymptotically matches the best-known upper bounds.
Our second contribution are new bounds on the size of Graver elements and on the proximity for ILPs. We first show nearly tight lower and upper bounds for gmax(A), the maximal size ∥g∥1 of any Graver element g of the Graver basis of the matrix A. Finally, we show that the proximity of any ILP (A, b, c) in standard form with m constraints is bounded by m · gmax(A). Previous works proved such proximity bounds in terms of the number n of variables and gmax(A), however, m can be much smaller than n.
Subjects
Graver bases
Integer linear programming
proximity bounds
DDC Class
004: Computer Sciences