Thumbnail - Request a copy

Algorithms and applications for a class of bilevel MILPs

Poirion, Pierre-Louis; Toubaline, Sónia; D'Ambrosio, Claudia; Liberti, Leo (2018), Algorithms and applications for a class of bilevel MILPs, Discrete Applied Mathematics. 10.1016/j.dam.2018.02.015

Type
Article accepté pour publication ou publié
Date
2018
Journal name
Discrete Applied Mathematics
Publisher
Elsevier
Publication identifier
Metadata
Show full item record
Author(s)
Poirion, Pierre-Louis
autre
Toubaline, Sónia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
D'Ambrosio, Claudia cc
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
Liberti, Leo cc
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
Abstract (EN)
We study a class of bilevel mixed-integer linear programs with the following restrictions: all upper level variables x are binary, the lower level variables y occur in exactly one upper level constraint γx+βy≥c, and the lower level objective function is minyβy. We propose a new cut generation algorithm to solve this problem class, based on two simplifying assumptions. We then propose a row-and-column generation algorithm that works independently of the assumptions. We apply our methods to two problems: one is related to the optimal placement of measurement devices in an electrical network, and the other is the minimum zero forcing set problem, a variant of the dominating set problem. We exhibit computational results of both methods on the application-oriented instances as well as on randomly generated instances.
Subjects / Keywords
Bilevel MILP; Power edge set; Zero forcing set