View article

Jeroslow and Lowe gave an exact geometric characterization of subsets of that are projections of mixed-integer linear sets, also known as MILP-representable or MILP-R sets. We give an alternate algebraic characterization by showing that a set is MILP-R if and only if the set can be described as the intersection of finitely many affine Chvátal inequalities in continuous variables (termed AC sets). These inequalities are a modification of a concept introduced by Blair and Jeroslow. Unlike the case for linear inequalities, allowing for integer variables in Chvátal inequalities and projection does not enhance modeling power. We show that the MILP-R sets are still precisely those sets that are modeled as affine Chvátal inequalites with integer variables. Furthermore, the projection of a set defined by affine Chvátal inequalites with integer variables is still a MILP-R set. We give a sequential variable elimination scheme that …