Jeroslow and Lowe gave an exact geometric characterization of subsets of R~n that are projections of mixed-integer linear sets, a.k.a MILP-representable sets. We give an alternate algebraic characterization by showing that a set is MILP-representable if and only if the set can be described as the intersection of finitely many affine Chvatal inequalities. These inequalities are a modification of a concept introduced by Blair and Jeroslow. This gives a sequential variable elimination scheme that, when applied to the MILP representation of a set, explicitly gives the affine Chvatal inequalities characterizing the set. This is related to the elimination scheme of Wiliams and Williams-Hooker, who describe projections of integer sets using disjunctions of affine Chvatal systems. Our scheme extends their work in two ways. First, we show that disjunctions are unnecessary, by showing how to find the affine Chvatal inequalities that cannot be discovered by the Williams-Hooker scheme. Second, disjunctions of Chvatal systems can give sets that are not projections of mixed-integer linear sets; so the Williams-Hooker approach does not give an exact characterization of MILP representability.
展开▼
