Infeasibility Certificates from Superadditive Functions for Mixed-Integer Programs

We present a constructive procedure for certifying the infeasibility of a mixed-integer program (MIP) using recursion on a sequence of sets that describe the sets of barely feasible right-hand sides. Each of these sets corresponds to a monotonic superadditive function, and the pointwise limit of this sequence is a functional certificate for MIP infeasibility. Our set recursion terminates correctly in finite time when integer variables are bounded. Dual cone vectors provide pruning conditions to eliminate lower levels of the recursion.