2425. Mixed-Integer Optimization Techniques for Robust Bilevel Problems with Here-and-Now Followers
Invited abstract in session TC-4: GOR PhD Awards, stream PC Stream.
Thursday, 11:45-13:15Room: H6
Authors (first author is the speaker)
| 1. | Yasmine Beck
|
| Eindhoven University of Technology |
Abstract
In bilevel optimization, some variables of an optimization problem have to be an optimal solution to another nested optimization problem. This structure makes bilevel problems a powerful tool for modeling hierarchical decision-making processes, which arise in various real-world applications such as in critical infrastructure defense, transportation, or energy. However, as they combine two different decision-makers in a single model, bilevel problems are inherently hard to solve. Further challenges arise if problems under uncertainty are considered.
In this work we highlight that the sources of uncertainty in bilevel optimization are much richer compared to single-level optimization because not only the problem data but also the (observation of the) decisions of the two players can be uncertain. The main goal of this work is the development of algorithmic approaches to solve bilevel problems in which techniques from robust optimization are used to address uncertainties. First, we present exact branch-and-cut and heuristic methods for mixed-integer linear bilevel problems with a Gamma-robust treatment of objective uncertainty. The efficiency of our methods is assessed through extensive computational studies. Second, we study the problem of determining optimal tolls in a traffic network in which travelers hedge against uncertain travel costs in a robust way. We formulate this problem as a mathematical program with equilibrium constraints, for which we present a reformulation that can be tackled using state-of-the-art general-purpose solvers. We further illustrate the impact of accounting for uncertainties on toll policies and travelers' behavior through a case study. Third and finally, we discuss two aspects related to decision uncertainty in bilevel optimization.
Keywords
- Global Optimization
- Mixed-Integer Programming
- Robust Optimization
Status: accepted
Back to the list of papers