Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
From MaRDI portal
Publication:2197489
DOI10.1016/J.DAM.2020.07.011zbMATH Open1450.90042arXiv1910.12608OpenAlexW3045723015MaRDI QIDQ2197489FDOQ2197489
Authors: Marc Goerigk, Jannis Kurtz, Michael Poss 
Publication date: 31 August 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1910.12608
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Price of Robustness
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
- The complexity of finding two disjoint paths with min-max objective function
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Robust convex optimization
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- The complexity of finding maximum disjoint paths with length constraints
- Robust combinatorial optimization with variable budgeted uncertainty
- Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty
- Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty
- Min-max-min robust combinatorial optimization
- Finite Adaptability in Multistage Linear Optimization
- Title not available (Why is that?)
- Computing robust basestock levels
- K-Adaptability in Two-Stage Robust Binary Programming
- Robust combinatorial optimization with knapsack uncertainty
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- \(K\)-adaptability in two-stage mixed-integer robust optimization
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Robust Discrete Optimization Problems with the WOWA Criterion
- $K$-adaptability in two-stage distributionally robust binary programming
- Two-stage combinatorial optimization problems under risk
Cited In (11)
- 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
- Min-Max-Min Optimization with Smooth and Strongly Convex Objectives
- Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
- Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions
- A double-oracle, logic-based Benders decomposition approach to solve the \(K\)-adaptability problem
- Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
- Min-max-min robust combinatorial optimization
- Recycling inequalities for robust combinatorial optimization with budget uncertainty
- A Lagrangian dual method for two-stage robust optimization with binary uncertainties
- A single representative min-max-min robust selection problem with alternatives and budgeted uncertainty
Uses Software
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)
