SENSITIVITY THEOREMS IN INTEGER LINEAR-PROGRAMMING

We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program max left brace w chi : A chi b right brace , the distance to the nearest optimal solution to the corresponding integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral matrix A. Using this, we strengthen several integer programming 'proximity' results. We also show that the Chvatal rank of a polyhedron left brace chi : A chi less than equivalent to b right brace can be bounded above by a function of the matrix A, independent of the vector b.