Compromise solutions for robust combinatorial optimization with variable-sized uncertainty
From MaRDI portal
Abstract: In classic robust optimization, it is assumed that a set of possible parameter realizations, the uncertainty set, is modeled in a previous step and part of the input. As recent work has shown, finding the most suitable uncertainty set is in itself already a difficult task. We consider robust problems where the uncertainty set is not completely defined. Only the shape is known, but not its size. Such a setting is known as variable-sized uncertainty. In this work we present an approach how to find a single robust solution, that performs well on average over all possible uncertainty set sizes. We demonstrate that this approach can be solved efficiently for min-max robust optimization, but is more involved in the case of min-max regret, where positive and negative complexity results for the selection problem, the minimum spanning tree problem, and the shortest path problem are provided. We introduce an iterative solution procedure, and evaluate its performance in an experimental comparison.
Recommendations
- Robust combinatorial optimization with variable cost uncertainty
- Robust combinatorial optimization with variable budgeted uncertainty
- Mixed uncertainty sets for robust combinatorial optimization
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Robust combinatorial optimization with knapsack uncertainty
- Solving robust two-stage combinatorial optimization problems under convex uncertainty
- Robust combinatorial optimization with locally budgeted uncertainty
- Combinatorial optimization under uncertainty
- Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
- On the robustness of optimal solutions for combinatorial optimization problems
Cites work
- scientific article; zbMATH DE number 193123 (Why is no real title available?)
- A variational approach to define robustness for parametric multiobjective optimization problems
- An approximation algorithm for interval data minmax regret combinatorial optimization problems
- An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax-regret criterion
- Constructing uncertainty sets for robust linear optimization
- Data-driven robust optimization
- Distributionally Robust Convex Optimization
- Distributionally robust optimization and its tractable approximations
- Interval data minmax regret network optimization problems
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights
- Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets
- On the approximability of robust spanning tree problems
- Randomized minmax regret for combinatorial optimization under uncertainty
- Recent advances in robust optimization: an overview
- Robust convex optimization
- Robust optimization
- Robust optimization-methodology and applications
- Robust solutions of linear programming problems contaminated with uncertain data
- Robust solutions of uncertain linear programs
- Robustness analysis in decision aiding, optimization, and analytics
- The robust spanning tree problem with interval data
- Theory and applications of robust optimization
- Variable-sized uncertainty and inverse problems in robust optimization
Cited in
(4)
This page was built for publication: Compromise solutions for robust combinatorial optimization with variable-sized uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1750469)
