AA3 – Networks

Project

AA3-1

Proximity of LP and IP solutions

Project Heads

Martin Henk

Project Members

Marcel Celaya (TU)

Project Duration

01.01.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

Selected Pictures

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.