A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs

Matteo Fischetti (), Ivana Ljubić (), Michele Monaci () and Markus Sinnl ()
Additional contact information
Matteo Fischetti: Department of Information Engineering, University of Padua, 35131 Padova, Italy
Ivana Ljubić: ESSEC Business School of Paris, 95021 Cergy-Pontoise, France
Michele Monaci: DEI “Guglielmo Marconi”, University of Bologna, 40136 Bologna, Italy
Markus Sinnl: Department of Statistics and Operations Research, University of Vienna, 1090 Vienna, Austria

Operations Research, 2017, vol. 65, issue 6, 1615-1637

Abstract: Bilevel optimization problems are very challenging optimization models arising in many important practical contexts, including pricing mechanisms in the energy sector, airline and telecommunication industry, transportation networks, critical infrastructure defense, and machine learning. In this paper, we consider bilevel programs with continuous and discrete variables at both levels, with linear objectives and constraints (continuous upper level variables, if any, must not appear in the lower level problem). We propose a general-purpose branch-and-cut exact solution method based on several new classes of valid inequalities, which also exploits a very effective bilevel-specific preprocessing procedure. An extensive computational study is presented to evaluate the performance of various solution methods on a common testbed of more than 800 instances from the literature and 60 randomly generated instances. Our new algorithm consistently outperforms (often by a large margin) alternative state-of-the-art methods from the literature, including methods exploiting problem-specific information for special instance classes. In particular, it solves to optimality more than 300 previously unsolved instances from the literature. To foster research on this challenging topic, our solver is made publicly available online.

Keywords: bilevel optimization; mixed-integer programming; cutting planes; intersection cuts; branch and cut; computational analysis (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (41)

Downloads: (external link)
https://doi.org/10.1287/opre.2017.1650 (application/pdf)

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:inm:oropre:v:65:y:2017:i:6:p:1615-1637

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().