Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty
From MaRDI portal
Publication:2125227
Abstract: In this paper a class of robust two-stage combinatorial optimization problems is discussed. It is assumed that the uncertain second stage costs are specified in the form of a convex uncertainty set, in particular polyhedral or ellipsoidal ones. It is shown that the robust two-stage versions of basic network and selection problems are NP-hard, even in a very restrictive cases. Some exact and approximation algorithms for the general problem are constructed. Polynomial and approximation algorithms for the robust two-stage versions of basic problems, such as the selection and shortest path problems, are also provided.
Recommendations
- Solving robust two-stage combinatorial optimization problems under convex uncertainty
- Two-stage robust optimization problems with two-stage uncertainty
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Two-stage robust mixed integer programming problem with objective uncertainty
- Robust combinatorial optimization with variable cost uncertainty
- On 2-stage robust LP with RHS uncertainty: complexity results and applications
- Two-stage combinatorial optimization problems under risk
- Robust two-stage stochastic linear programs with moment constraints
- Robust combinatorial optimization with variable budgeted uncertainty
- On robust optimization of two-stage systems
Cites work
- K-adaptability in two-stage robust binary programming
- A survey of adjustable robust optimization
- Adjustable robust solutions of uncertain linear programs
- Algorithms and complexity analysis for robust single-machine scheduling problems
- An approximation scheme for stochastic linear programming and its application to stochastic integer programs
- An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax-regret criterion
- Approximability of the robust representatives selection problem
- Branch-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty
- Commitment under uncertainty: Two-stage stochastic matching problems
- Complexity and in-approximability of a selection problem in robust optimization
- Geometric algorithms and combinatorial optimization.
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- Min-max and min-max (relative) regret approaches to representatives selection problem
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Min-max-min robust combinatorial optimization
- Network flows. Theory, algorithms, and applications.
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- On the approximability of minmax (regret) network optimization problems
- On the approximability of robust spanning tree problems
- On the complexity of a class of combinatorial optimization problems with uncertainty
- On the random 2-stage minimum spanning tree
- On Two-Stage Stochastic Minimum Spanning Trees
- Recoverable robust shortest path problems
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Robust combinatorial optimization with knapsack uncertainty
- Robust combinatorial optimization with locally budgeted uncertainty
- Robust optimization
- Robust optimization approach for a chance-constrained binary knapsack problem
- Robust optimization of sums of piecewise linear functions with application to inventory problems
- Robust recoverable and two-stage selection problems
- Robust solutions of uncertain linear programs
- Solving two-stage robust optimization problems using a column-and-constraint generation method
- The Price of Robustness
- Two-stage combinatorial optimization problems under risk
Cited in
(14)- Solving robust two-stage combinatorial optimization problems under convex uncertainty
- Two-stage robust optimization problems with two-stage uncertainty
- Two-stage robust optimization for the orienteering problem with stochastic weights
- Combinatorial two-stage minmax regret problems under interval uncertainty
- Two-stage combinatorial optimization problems under risk
- Two-stage robust optimization, state-space representable uncertainty and applications
- On the complexity of robust multi-stage problems with discrete recourse
- Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints
- On 2-stage robust LP with RHS uncertainty: complexity results and applications
- Combinatorial robust optimization with decision-dependent information discovery and polyhedral uncertainty
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard
- Data-driven prediction of relevant scenarios for robust combinatorial optimization
- Robust combinatorial optimization problems under budgeted interdiction uncertainty
This page was built for publication: Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2125227)
