Computing the integer programming gap (Q2460632)

The problem considered in this paper is the determination of the gap between the optimal solution of an integer programming problem and its linear programming relaxation. The authors give a formula for this gap (or, more precisely, for its generating function over the right hand sides of the problem) as a rational function. The results are applied to the problem of disclusure limitation in algebraic statistics. Finally, for a fixed coefficient matrix the gap function is shown to be piecewise linear, the sections of space on which this function is linear being a refinement of the Gröbner fan of an ideal related to this integer/linear programming problem.