Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets
From MaRDI portal
Abstract: We consider robust counterparts of uncertain combinatorial optimization problems, where the difference to the best possible solution over all scenarios is to be minimized. Such minmax regret problems are typically harder to solve than their nominal, non-robust counterparts. While current literature almost exclusively focuses on simple uncertainty sets that are either finite or hyperboxes, we consider problems with more flexible and realistic ellipsoidal uncertainty sets. We present complexity results for the unconstrained combinatorial optimization problem and for the shortest path problem. To solve such problems, two types of cuts are introduced, and compared in a computational experiment.
Recommendations
- Minmax regret solutions for minimax optimization problems with uncertainty
- Randomized minmax regret for combinatorial optimization under uncertainty
- Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios
- Robust combinatorial optimization under budgeted-ellipsoidal uncertainty
- Computing Min-Max Regret Solutions in Possibilistic Combinatorial Optimization Problems
- Combinatorial two-stage minmax regret problems under interval uncertainty
- Minmax regret combinatorial optimization problems: an algorithmic perspective
- A Probabilistic Model for Minmax Regret in Combinatorial Optimization
- Minmax regret bottleneck problems with solution-induced interval uncertainty structure
- Min max min robust (relative) regret combinatorial optimization
Cites work
- A branch and bound algorithm for the robust shortest path problem with interval data.
- A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
- A relaxation algorithm with a probabilistic guarantee for robust deviation optimization
- An approximation algorithm for interval data minmax regret combinatorial optimization problems
- Approximation of min-max and min-max regret versions of some combinatorial optimization problems
- Complexity of the min-max and min-max regret assignment problems
- Interval data minmax regret network optimization problems
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Minimax regret solution to linear programming problems with an interval objective function
- On a constant factor approximation for minmax regret problems using a symmetry point scenario
- On exact solutions for the minmax regret spanning tree problem
- On the complexity of a class of combinatorial optimization problems with uncertainty
- On the complexity of minmax regret linear programming
- On the robust shortest path problem.
- Robust convex optimization
- Robust discrete optimization and its applications
- Robust optimization
- Robust solutions of uncertain linear programs
- The Price of Robustness
- Theory and applications of robust optimization
Cited in
(14)- Project net present value estimation under uncertainty
- Benchmarking problems for robust discrete optimization
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Variable-sized uncertainty and inverse problems in robust optimization
- Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios
- A Probabilistic Model for Minmax Regret in Combinatorial Optimization
- On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
- Minmax regret combinatorial optimization problems: an algorithmic perspective
- Minmax regret solutions for minimax optimization problems with uncertainty
- Combinatorial optimization problems with balanced regret
- Robust combinatorial optimization under budgeted-ellipsoidal uncertainty
- Compromise solutions for robust combinatorial optimization with variable-sized uncertainty
- Robust combinatorial optimization under convex and discrete cost uncertainty
- The impacts of retailers' regret aversion on a random multi-period supply chain network
This page was built for publication: Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1698883)
