Groupe d’études et de recherche en analyse des décisions

G-2004-13

New Branch-and-Cut Algorithm for Bilevel Linear Programming

, et

Linear mixed 0-1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0-1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts to reduce the size of the feasible region without eliminating the optimal solution. The second phase consists of a Branch-and-Bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection criterion and the branching criterion are studied in details. We also propose a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure Branch-and-Bound when tested on a series of randomly generated problems.

, 30 pages