New Branch-and-Cut Algorithm for Bilevel Linear Programming

C. Audet, G. Savard () and W. Zghal
Additional contact information
C. Audet: GERAD and École Polytechnique de Montréal
G. Savard: GERAD and École Polytechnique de Montréal
W. Zghal: GERAD and École Polytechnique de Montréal

Journal of Optimization Theory and Applications, 2007, vol. 134, issue 2, No 12, 353-370

Abstract: Abstract 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.

Keywords: Bilevel linear programming; Gomory cuts; Linear mixed 0–1 integer programming; Branch-and-cut algorithms (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-007-9263-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:134:y:2007:i:2:d:10.1007_s10957-007-9263-4

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-007-9263-4

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().