AA3 – Networks

Project

AA3-1

Proximity of LP and IP Solutions

Project Heads

Martin Henk

Project Members

Marcel Celaya (TU)

Project Duration

01.08.2019 – 31.12.2020

Located at

TU Berlin

Description

A classic result of Cook et al. (1986) bounds the distances between optimal solutions of integer linear programs and optimal solutions of the corresponding linear relaxations. Their bound is the product of the dimension and a parameter Δ, which quantifies sub-determinants of the underlying linear inequalities. We intend to study this bound both, deterministically and probabilistically. In particular, in the deterministic setting we want to make the bound independent of the dimension.  This would be a first step to show that Δ is a fundamental parameter to make high dimensional integer linear optimization problems tractable.

Project Webpages

Selected Publications

  • I. Aliev, M. Celaya, M. Henk, and A. Williams. Distance-sparsity transference for vertices of corner polyhedra. SIAM J. Optim. 2021, 31(1), 2021, 200–216; arXiv:2007.00950
  • M. Celaya and M. Henk. Proximity bounds for random integer programs. In: Integer Programming and Combinatorial Optimization, 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings (pp.413-426)
  • I. Aliev, M. Henk, and T. Oertel. Integrality gaps of integer knapsack problems. In Integer programming and combinatorial optimization, volume 10328 of Lecture Notes in Comput. Sci., pages 25–38. Springer, Cham, 2017.

  • W. Cook, A.M.H. Gerards, A. Schrijver, and E. Tardos. Sensitivity theorems in integer linear programming. Math. Programming, 34(3):251–264, 1986.

  • F. Eisenbrand and R. Weismantel. Proximity results and faster algorithms for integer pro- gramming using the Steinitz lemma. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 808–816. SIAM, Philadelphia, PA, 2018.

Selected Pictures

Red dots are the integral optimal solutions whereas X* is the fractional optimal solution.

Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)

As Title in the above form please add a copyright.

And please give a short description of the picture and the context in the above textbox.

Don’t forget to press the “Save changes” button at the bottom of the box.

If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.