Delta-only distance conjecture for optimal mixed-integer program solutions

Let AA be the constraint matrix, let Δ\Delta be the largest absolute value of any determinant of a square submatrix of AA, and let I,J[n]I,J\subseteq[n] index the variables required to be integer in the mixed-integer programs (I-MIP)(I\text{-MIP}) and (J-MIP)(J\text{-MIP}). Assume that (J-MIP)(J\text{-MIP}) has an optimal solution. Delta-only distance conjecture. There exists a function

f:Z1Rf:\mathbb{Z}_{\ge 1}\to\mathbb{R}

such that, for every optimal solution ww of (I-MIP)(I\text{-MIP}), there exists an optimal solution zz of (J-MIP)(J\text{-MIP}) satisfying

wzf(Δ).\lVert w-z\rVert_{\infty}\le f(\Delta).

The paper proves a bound depending on Δ\Delta and IJ|I\cup J|, and conjectures that the dependence on the number of integer variables can be removed entirely. It is not known whether distances between optimal solutions can always be bounded solely in terms of Δ\Delta.

Sources & referencesView supporting material

Primary source

Joseph Paat, Robert Weismantel and Stefan Weltge, “Distances of optimal solutions of mixed-integer programs”, arXiv:1801.08751 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.