Closing the gap in linear bilevel optimization: a new valid primal-dual inequality
- PDF / 512,119 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 20 Downloads / 157 Views
Closing the gap in linear bilevel optimization: a new valid primal-dual inequality Thomas Kleinert1,2 · Martine Labbé3,4 · Fränk Plein3,4 · Martin Schmidt5 Received: 5 June 2020 / Accepted: 29 October 2020 © The Author(s) 2020
Abstract Linear bilevel optimization problems are often tackled by replacing the linear lowerlevel problem with its Karush–Kuhn–Tucker conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bileveltailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.
B
Martin Schmidt [email protected] Thomas Kleinert [email protected] Martine Labbé [email protected] Fränk Plein [email protected]
1
Friedrich-Alexander-Universität Erlangen-Nürnberg, Discrete Optimization, Cauerstr. 11, 91058 Erlangen, Germany
2
Energie Campus Nürnberg, Fürther Str. 250, 90429 Nürnberg, Germany
3
Department of Computer Science, Université Libre de Bruxelles, Boulevard du Triomphe, CP212, 1050 Brussels, Belgium
4
Inria Lille-Nord Europe, Parc scientifique de la Haute Borne, 40, av. Halley - Bât A - Park Plaza, 59650 Villeneuve d’Ascq, France
5
Department of Mathematics, Trier University, Universitätsring 15, 54296 Trier, Germany
123
T. Kleinert et al.
Keywords Bilevel optimization · Valid inequalities · Branch-and-cut · Computational analysis Mathematics Subject Classification 90Cxx · 90-08 · 90C11 · 90C46
1 The difficulty in closing the optimality gap Roughly speaking, branch-and-bound algorithms solve mathematical optimization problems by successively finding lower and upper bounds on the optimal objective function value. This procedure progressively decreases the optimality gap, i.e., the difference of the two bounds, until it is closed and the lower and upper bound meet. For minimization problems, every primal feasible solution provides a valid upper bound on the objective function value. Lower bounds in turn are computed by solving relaxations of the original problem. While modern branch-and-bound algorithms may find good primal solutions quickly, proving optimality by closing the optimality gap might be very challenging. It is not unusual to observe solution processes similar to the dashed line in Fig. 1, which shows an exemplary evolution of the lower and upper bounds over the number of visited nodes provided by a branch-and-bound implementation. An almost optimal
Data Loading...