Distances between optimal solutions of mixed-integer programs

A classic result of Cook et al. (Math. Program. 34:251–264, 1986) bounds the distances between optimal solutions of mixed-integer linear programs and optimal solutions of the corresponding linear relaxations. Their bound is given in terms of the number of variables and a parameter Δ, which quantifies sub-determinants of the underlying linear inequalities. We show that this distance can be bounded in terms of Δ and the number of integer variables rather than the total number of variables. To this end, we make use of a result by Olson (J. Number Theory 1:8–10, 1969) in additive combinatorics and demonstrate how it implies feasibility of certain mixed-integer linear programs. We conjecture that our bound can be improved to a function that only depends on Δ, in general.