• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

A New General-Purpose Algorithm for ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Article dans une revue scientifique
DOI :
10.1287/opre.2017.1650
Title :
A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
Author(s) :
Fischetti, Matteo [Auteur]
Dipartimento di Ingegneria de l'Informazione [Padova] [DEI]
Ljubić, Ivana [Auteur]
Essec Business School
Monaci, Michele [Auteur]
Sinnl, Markus [Auteur]
University of Vienna [Vienna]
Integrated Optimization with Complex Structure [INOCS]
Journal title :
Operations Research
Pages :
1615 - 1637
Publisher :
INFORMS
Publication date :
2017-12
ISSN :
0030-364X
HAL domain(s) :
Informatique [cs]/Recherche opérationnelle [cs.RO]
English abstract : [en]
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 ...
Show more >
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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://cris.unibo.it/bitstream/11585/611023/3/Bilevel_post-print_new.pdf
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017