Proximity and Integrality-Gap Bounds for Convex Mixed-Integer Programs
Upper bounds on the proximity (distance between the optimal solutions of a convex integer program and its continuous relaxation) and on the integrality gap, expressed through the recession cone of the relaxation's feasible region. The results specialize to second-order (Lorentz) conic integer programs, bounding both quantities in terms of the problem data and the covering radius of an associated lattice, with conditions for the bounds to be independent of the right-hand side.
2501.00638
Studies proximity and the integrality gap for convex integer programs: how far the optimal solution can move, and how much the optimal value can change, when variables are forced to be integral rathe…