Operations Research 2025
Abstract Submission

56. A Branch-and-Cut Approach for Decision-Dependent Robust Optimization Problems

Invited abstract in session WE-2: Decomposition Methods & Robust Optimization, stream Discrete and Combinatorial Optimization.

Wednesday, 16:30-18:00
Room: H4

Authors (first author is the speaker)

1. Simon Stevens
Department of Mathematics, Trier University
2. Henri Lefebvre
Department of Mathematics, Universität Trier
3. Martin Schmidt
Department of Mathematics, Trier University
4. Johannes Thürauf
Discrete Optimization, University of Technology Nuremberg

Abstract

Compared to classic robust optimization, decision-dependent robust optimization (DDRO) models the uncertainties as being dependent on the decision variables, thus enabling some control over these uncertainties within the model. The literature on DDRO is still limited and most of the existing solution techniques rely on reformulations using duality. Hence, they are naturally restricted to uncertainty sets that can be dualized. Recent results by Goerigk et al. (2025) show that DDRO problems can be reformulated as bilevel optimization problems, opening up new possibilities for solving this class of problems. First numerical results by Lefebvre et al. (2025) indicate that applying general bilevel solvers like MibS to DDRO problems for which the uncertainty set cannot be dualized is possible in general, though not efficient.

We present a tailored branch-and-cut approach for solving DDRO problems in which the uncertainty set is given by an interdicted knapsack problem. To this end, we tailor an interdiction-like cutting plane from the bilevel literature, which is incorporated in the branch-and-cut framework. We present numerical results on a set of benchmark instances and compare our approach with the existing general bilevel solver MibS. The results demonstrate that our approach is significantly faster and capable of solving larger DDRO instances.

Keywords

Status: accepted

Back to the list of papers