Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.dam.2018.02.015 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Bilevel MILP,Power edge set,Zero forcing set | Discrete mathematics,Dominating set,Combinatorics,Electrical network,Algorithm,Zero Forcing Equalizer,Mathematics,Binary number | Journal |
Volume | ISSN | Citations |
272 | 0166-218X | 1 |
PageRank | References | Authors |
0.35 | 14 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pierre-Louis Poirion | 1 | 24 | 7.43 |
Sonia Toubaline | 2 | 60 | 7.54 |
Claudia D'Ambrosio | 3 | 159 | 20.07 |
Leo Liberti | 4 | 1280 | 105.20 |