Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
From MaRDI portal
(Redirected from Publication:2197489)
Abstract: We consider robust combinatorial optimization problems with cost uncertainty where the decision maker can prepare K solutions beforehand and chooses the best of them once the true cost is revealed. Also known as min-max-min robustness (a special case of K-adaptability), it is a viable alternative to otherwise intractable two-stage problems. The uncertainty set assumed in this paper considers that in any scenario, at most Gamma of the components of the cost vectors will be higher than expected, which corresponds to the extreme points of the budgeted uncertainty set. While the classical min-max problem with budgeted uncertainty is essentially as easy as the underlying deterministic problem, it turns out that the min-max-min problem is NPhard for many easy combinatorial optimization problems, and not approximable in general. We thus present an integer programming formulation for solving the problem through a row-and-column generation algorithm. While exact, this algorithm can only cope with small problems, so we present two additional heuristics leveraging the structure of budgeted uncertainty. We compare our row-and-column generation algorithm and our heuristics on knapsack and shortest path instances previously used in the scientific literature and find that the heuristics obtain good quality solutions in short computational times.
Recommendations
- Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty
- On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
- Min-max-min robust combinatorial optimization
- Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
- Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2102031 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- $K$-adaptability in two-stage distributionally robust binary programming
- Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty
- Computing robust basestock levels
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty
- Finite Adaptability in Multistage Linear Optimization
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Min-max-min robust combinatorial optimization
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Robust combinatorial optimization with knapsack uncertainty
- Robust combinatorial optimization with variable budgeted uncertainty
- Robust convex optimization
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Robust discrete optimization problems with the WOWA criterion
- Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
- The Price of Robustness
- The complexity of finding maximum disjoint paths with length constraints
- The complexity of finding two disjoint paths with min-max objective function
- Two-stage combinatorial optimization problems under risk
- \(K\)-adaptability in two-stage mixed-integer robust optimization
- K-adaptability in two-stage robust binary programming
Cited in
(19)- A single representative min-max-min robust selection problem with alternatives and budgeted uncertainty
- Graph coloring approaches for a production planning problem with makespan and setup penalties in a product-wheel context
- Approximation guarantees for min-max-min robust optimization and \(k\)-adaptability under objective uncertainty
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- Data-driven prediction of relevant scenarios for robust combinatorial optimization
- Robust combinatorial optimization with variable cost uncertainty
- Min-Max-Min Optimization with Smooth and Strongly Convex Objectives
- Robust combinatorial optimization with locally budgeted uncertainty
- Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
- Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions
- Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
- A double-oracle, logic-based Benders decomposition approach to solve the \(K\)-adaptability problem
- On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
- Min-max-min robust combinatorial optimization
- Recycling inequalities for robust combinatorial optimization with budget uncertainty
- Robust combinatorial optimization with variable budgeted uncertainty
- Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty
- A Lagrangian dual method for two-stage robust optimization with binary uncertainties
- Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty
This page was built for publication: Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197489)
