Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
Operations Research · 1987 · Volume 35 · Issue 6
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.
Keywords
630 LP-based branch-and-bound, 639 theory of variable redefinition
Enable JavaScript for citation tools and additional paper interactions.