Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition

Abstract

Dropping the “complicating” constraints in a mixed-integer linear program often yields a “special structure subproblem” that can be reformulated using a different set of decision variables. Once the new variables have been identified, the entire problem can be reformulated in terms of the new variables. We develop a theory of variable redefinition based on relating the two sets of decision variables by a linear transformation, and describe methods for reformulating the special structure problem. The reformulated models have a more accurate linear relaxation than the problems from which they were derived, an important property within the context of linear programming-based branch-and-bound modeling approaches.