The value function of a mixed integer program: II

AbstractWe prove that the gap in optimal value, between a mixed-integer program in rationals and its corresponding linear programming relaxation, is bounded as the right-hand-side is varied. In addition, a variant of value iteration is shown to construct subadditive functions which resolve a pure-integer program when no dual degeneracy occurs. These subadditive functions provide solutions to subadditive dual programs for integer programs which are given here, and for which the values of primal and dual problems are equal