caa a22 4500 463169360 CHVBK 20180406164808.0 cr unu---uuuuu 170326e20070801xx s 000 0 eng 10.1007/s10957-007-9263-4 doi (NATIONALLICENCE)springer-10.1007/s10957-007-9263-4 New Branch-and-Cut Algorithm for Bilevel Linear Programming [Elektronische Daten] [C. Audet, G. Savard, W. Zghal] 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. 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 and branching criteria are studied in details. We propose also 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. Springer Science+Business Media, LLC, 2007 Bilevel linear programming nationallicence Gomory cuts nationallicence Linear mixed 0-1 integer programming nationallicence Branch-and-cut algorithms nationallicence Audet C. GERAD and École Polytechnique de Montréal, Montreal, PQ, Canada aut Savard G. GERAD and École Polytechnique de Montréal, Montreal, PQ, Canada aut Zghal W. GERAD and École Polytechnique de Montréal, Montreal, PQ, Canada aut Journal of Optimization Theory and Applications Springer US; http://www.springer-ny.com 134/2(2007-08-01), 353-370 0022-3239 134:2<353 2007 134 10957 https://doi.org/10.1007/s10957-007-9263-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10957-007-9263-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Audet C. GERAD and École Polytechnique de Montréal, Montreal, PQ, Canada aut NATIONALLICENCE 700 1- Savard G. GERAD and École Polytechnique de Montréal, Montreal, PQ, Canada aut NATIONALLICENCE 700 1- Zghal W. GERAD and École Polytechnique de Montréal, Montreal, PQ, Canada aut NATIONALLICENCE 773 0- Journal of Optimization Theory and Applications Springer US; http://www.springer-ny.com 134/2(2007-08-01), 353-370 0022-3239 134:2<353 2007 134 10957 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer