583. Exact and Heuristic Methods for Gamma-Robust Mixed-Integer Linear Min-Max Problems
Invited abstract in session MA-17: Combinatorial bilevel optimization 1, stream Combinatorial Optimization.
Monday, 8:30-10:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Yasmine Beck
|
| Eindhoven University of Technology | |
| 2. | Ivana Ljubic
|
| IDS, ESSEC Business School of Paris | |
| 3. | Martin Schmidt
|
| Department of Mathematics, Trier University |
Abstract
Due to their nested structure, bilevel problems are intrinsically hard to solve—even if all variables are continuous and all parameters of the problem are exactly known. In this talk, we study mixed-integer linear min-max problems with a binary lower level and a Gamma-robust treatment of lower-level objective uncertainty. We present an exact branch-and-cut approach to solve these Gamma-robust min-max problems, along with cuts tailored to the important class of monotone interdiction problems. Given the overall hardness of the considered problems, we additionally present a heuristic approach. The latter relies on solving a linear number of deterministic min-max problems so that no problem-specific tailoring is required. The performance of our approaches is assessed in an extensive computational study on instances of the Gamma-robust knapsack interdiction problem. Our results show that the heuristic closes the optimality gap for a significant portion of the considered instances and that it often practically outperforms both heuristic and exact benchmark approaches. In particular, we report considerable speed-up factors when compared to our problem-tailored and exact branch-and-cut approach, while also solving more instances to global optimality.
Keywords
- Branch and Cut
- Global Optimization
- Robust Optimization
Status: accepted
Back to the list of papers