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.

A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs / Fischetti, M.; Ljubic, I.; Monaci, Michele; Sinnl, M.. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 65:6(2017), pp. 1615-1637. [10.1287/opre.2017.1650]

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

M. Monaci;
2017

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.
2017
A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs / Fischetti, M.; Ljubic, I.; Monaci, Michele; Sinnl, M.. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 65:6(2017), pp. 1615-1637. [10.1287/opre.2017.1650]
Fischetti, M.; Ljubic, I.; Monaci, Michele; Sinnl, M.
File in questo prodotto:
File Dimensione Formato  
Bilevel_post-print_new.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 915.5 kB
Formato Adobe PDF
915.5 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/611023
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 104
  • ???jsp.display-item.citation.isi??? 107
social impact