A Computational Study for Solving Decision-Dependent Robust Problems as Bilevel Optimization Problems
Henri Lefebvre, Martin Schmidt, Simon Stevens, Johannes Thürauf · 2025
Read A Computational Study for Solving Decision-Dependent Robust Problems as Bilevel Optimization Problems by Henri Lefebvre, Martin Schmidt, Simon Stevens, Johannes Thürauf (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01559.txt.
Introduction
Henri Lefebvre and three co-authors test a computing route for hard planning problems where the unknown set shifts with the choice made, in a 2025 paper. Such problems blend two known hard forms: robust planning under unknowns and two-level planning. Recent theory showed the two forms can be swapped. This study is the first wide test of that swap in practice.
When the unknown set can be flipped into a dual form, the swap yields larger problems and slower solves than classic tricks. When the unknown set is a mixed whole-number model, classic tricks fail outright. There the two-level route beat a known rival method on solve time. The authors map where each route pays.
Catalog record
| CREATOR | Henri Lefebvre, Martin Schmidt, Simon Stevens, Johannes Thürauf |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-01559
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Computational Study for Solving Decision-Dependent Robust Problems as Bilevel Optimization Problems Henri Lefebvre, Martin Schmidt, Simon Stevens, Johannes Thürauf Abstract . Both bilevel and robust optimization are established fields of mathematical optimization and operations research. However, only until recently, the similarities in their mathematical structure has neither been studied theoretically nor exploited computationally. Based on the recent results by [ 24 ] , this paper is the first one that provides an extensive computational study for solving strictly robust optimization problems with decision-dependent uncertainty sets as equivalent bilevel optimization problems. If the uncertainty set can be dualized, the respective bilevel techniques to obtain a single-level reformulation are very similar compared with the classic dualization techniques used in robust optimization but lead to larger single-level problems to be solved. Our numerical study shows that this usually leads to larger computation times. For the more challenging case of decision-dependent uncertainty sets represented by mixed-integer linear models, one cannot apply classic dualization techniques from robust optimization. Thus, we compare the presented bilevel approach with an established method from the literature, which is based on quantified mixed-integer linear programs. Our numerical results indicate that, for the problem class of decision-dependent robust optimization problems with mixed-integer linear uncertainty sets, the bilevel approach performs better in terms of computation times. 2020 Mathematics Subject Classification 90C70, 90C17, 91A65 1. Introduction Bilevel optimization deals with models of hierarchical decision making in which a so-called leader acts first, while anticipating the optimal reaction of the so-called follower, whose decision depends on the one of the leader. For a general overview of bilevel optimization we refer to [ 14 , 15 ] and the more recent surveys by [ 29 , 5 ] . Hence, the overall structure is that of a nested optimization problem. In robust optimization, one only considers a single-decision maker but explicitly takes into consideration that this agent has to make a decision under uncertainty. In classic robust optimization, the decision is taken before the uncertainty realizes and this uncertainty is assumed to realize in the worst-case sense, which again is represented by a nested optimization problem [ 44 , 8 ] . Hence, both types of problems—although being introduced to model completely different aspects of real-world decision making—exhibit a rather similar mathematical structure. To the best of our knowledge, the first publication in which this similarity has been observed is the one by [ 46 ] in the context of (generalized) semi-infinite optimization. Nevertheless, the literature on robust and bilevel optimization has been rather disjoint. Besides some comments in this direction by [ 32 ] , the first systematic study of the similarities and the differences of the mathematical structure of bilevel and robust optimization has been recently published by [ 24 ] . In particular, the authors show the equivalence of certain classes of robust and bilevel optimization problems, paving the way for using the computational methods from one field to solve problems from the other one. In this paper, we will exploit the particular equivalence between bilevel optimization and decision-dependent robust optimization to solve the latter, and present the first extensive computational study for this approach. One of the main concerns in robust optimization is to reduce the conservatism that is inherent to robust counterparts and their solutions. Many developments have thus focused on less conservative approaches for modeling the uncertainty sets, including polyhedral, ellipsoidal [ 9 ] or budgeted [ 11 ] uncertainty sets. These approaches often provide a more realistic representation of uncertainties, thereby resulting in less conservative solutions. In addition to traditional robust optimization, adaptive robust optimization and decision-dependent robust optimization (DDRO) have gained more attention in recent years. The former incorporates dynamic decision-making that adapts as uncertainties unfold, typically modeled using a multi-stage structure as in [ 10 ] and as in the survey by [ 49 ] . This approach may significantly reduce the conservatism of the model. DDRO addresses situations in which uncertainties are modeled as being dependent on the decision variables, enabling some control over these uncertainties within the model. Decision-dependent uncertainties are sometimes also called endogenous uncertainties and were initially introduced in the context of stochastic optimization problems; see, e.g., [ 28 ] . Since then, several papers on this topic have been published in the field of stochastic optimization [ 53 , 2 , 26 , 37 ] , to name just a few. Within robust optimization, however, the field of decision-dependent uncertainty is less mature. Notable methodological contributions include the work of [ 38 ] , who consider shortest-path problems with decision-dependent uncertainties in the arc lengths. They also show that even linear DDRO problems with polyhedral uncertainty sets and affine decision-dependence are NP-complete in general. Similarly, [ 41 , 42 ] examine combinatorial optimization problems such as the knapsack problem under budgeted uncertainty sets as well as under knapsack uncertainties. More recently, [ 31 ] study decision-dependent robust optimization problems in which uncertainty sets can be modified elementwise at a cost. Furthermore, decision-dependent robust optimization is also of interest in many application areas such as software partitioning [ 45 ] , scheduling [ 30 , 48 ] , energy networks [ 1 ] , or health care [ 55 ] . Finally, in recent years, decision-dependent uncertainties have also been explored within more specialized fields of robust optimization, such as two-stage and multistage robust optimization [ 54 , 3 , 52 , 12 ] or distributionally robust optimization [ 34 , 20 , 4 , 50 , 18 , 43 ] . To the best of our knowledge, most of the techniques to solve single-level DDRO problems rely on dualization or problem-specific knowledge to reformulate the robust optimization problem as a finite-dimensional problem consisting of finitely many variables and constraints. Consequently, these approaches are generally limited to cases with continuous and convex uncertainty sets that can be dualized, i.e., for which a strong-duality theorem is available. If such a theorem is not available, e.g., in cases in which the decision-dependent uncertainty set is represented as a mixed-integer linear model, the only well-maintained and publicly available code to solve the respective decision-dependent robust problems we are aware of is the Yasol solver for quantified mixed-integer problems [ 19 , 25 ] . More recently, new approaches have also been introduced by [ 33 ] . In particular, the authors present a column-and-constraint generation algorithm and a method based on decision diagrams. We use the recent result by [ 24 ] showing that decision-dependent robust optimization problems can be equivalently reformulated as bilevel optimization problems. Our main contribution is to present the first extensive computational study that illustrates the potential of solving DDRO problems as bilevel optimization problems. To this end, we consider classic operations-research problems that have already been studied in the literature on DDRO: the shortest-path problem, also considered by [ 38 ] in the DDRO setting, the knapsack problem, also considered by [ 41 , 42 ] in DDRO, and the portfolio optimization problem in its DDRO version. For the case of continuous and convex decision-dependent uncertainty sets, we derive the single-level reformulation of the corresponding bilevel problem, solve it, and compare it with solving the given problem using classic