Robust combinatorial optimization with locally budgeted uncertainty
From MaRDI portal
Publication:2165591
Abstract: Budgeted uncertainty sets have been established as a major influence on uncertainty modeling for robust optimization problems. A drawback of such sets is that the budget constraint only restricts the global amount of cost increase that can be distributed by an adversary. Local restrictions, while being important for many applications, cannot be modeled this way. We introduce new variant of budgeted uncertainty sets, called locally budgeted uncertainty. In this setting, the uncertain parameters become partitioned, such that a classic budgeted uncertainty set applies to each partition, called region. In a theoretical analysis, we show that the robust counterpart of such problems for a constant number of regions remains solvable in polynomial time, if the underlying nominal problem can be solved in polynomial time as well. If the number of regions is unbounded, we show that the robust selection problem remains solvable in polynomial time, while also providing hardness results for other combinatorial problems. In computational experiments using both random and real-world data, we show that using locally budgeted uncertainty sets can have considerable advantages over classic budgeted uncertainty sets.
Recommendations
- Robust combinatorial optimization with variable budgeted uncertainty
- Robust combinatorial optimization with variable cost uncertainty
- Robust combinatorial optimization under budgeted-ellipsoidal uncertainty
- Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty
- Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
Cites work
- Algorithms and uncertainty sets for data-driven robust shortest path problems
- Approximating multiobjective knapsack problems
- Complexity and in-approximability of a selection problem in robust optimization
- Data-driven robust optimization
- Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty
- scientific article; zbMATH DE number 3644795 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- New and improved bounds for the minimum set cover problem
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- Robust combinatorial optimization with knapsack uncertainty
- Robust combinatorial optimization with variable budgeted uncertainty
- Robust constrained shortest path problems under budgeted uncertainty
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Robust scheduling with budgeted uncertainty
- Some APX-completeness results for cubic graphs
- The Price of Robustness
- Two-stage robust optimization problems with two-stage uncertainty
Cited in
(10)- Robust combinatorial optimization under budgeted-ellipsoidal uncertainty
- Compromise solutions for robust combinatorial optimization with variable-sized uncertainty
- Robust combinatorial optimization with variable budgeted uncertainty
- Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty
- Mixed uncertainty sets for robust combinatorial optimization
- Robust combinatorial optimization with variable cost uncertainty
- Recycling inequalities for robust combinatorial optimization with budget uncertainty
- Short paper -- A note on robust combinatorial optimization with generalized interval uncertainty
- Combinatorial robust optimization with decision-dependent information discovery and polyhedral uncertainty
- Robust combinatorial optimization problems under budgeted interdiction uncertainty
This page was built for publication: Robust combinatorial optimization with locally budgeted uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2165591)
