Group for Research in Decision Analysis

G-95-20

Links Between the Linear Bilevel and Mixed 0-1 Programming Problems

, , , and

We study links between the bilevel linear and linear mixed 0-1 programming problems. A new reformulation of the linear mixed 0-1 programming problem into a bilevel linear programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0-1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0-1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation, i.e., when applied to any mixed 0-1 instance and it's bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation. Moreover, we deduce a new optimality test for bilevel linear programming which makes use of nonstandard penalties.

, 36 pages

This cahier was revised in December 1995