Delta-only distance conjecture for optimal mixed-integer program solutions
Delta-only distance conjecture for optimal mixed-integer program solutions
Let be the constraint matrix, let be the largest absolute value of any determinant of a square submatrix of , and let index the variables required to be integer in the mixed-integer programs and . Assume that has an optimal solution. Delta-only distance conjecture. There exists a function
such that, for every optimal solution of , there exists an optimal solution of satisfying
The paper proves a bound depending on and , 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 .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.