Two-stage combinatorial optimization problems under risk. (English) Zbl 1436.90122
Summary: In this paper a class of combinatorial optimization problems is discussed. It is assumed that a solution can be constructed in two stages. The current first-stage costs are precisely known, while the future second-stage costs are only known to belong to an uncertainty set, which contains a finite number of scenarios with known probability distribution. A partial solution, chosen in the first stage, can be completed by performing an optimal recourse action, after the true second-stage scenario is revealed. A solution minimizing the Conditional Value at Risk (CVaR) measure is computed. Since expectation and maximum are boundary cases of CVaR, the model generalizes the traditional stochastic and robust two-stage approaches, previously discussed in the existing literature. In this paper some new negative and positive results are provided for basic combinatorial optimization problems such as the selection or network problems.
Keywords:
combinatorial optimization; stochastic programming; two-stage problems; optimization under risk; robust optimizationReferences:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms, and Applications (1993), Prentice Hall: Prentice Hall Englewood Cliffs, New Jersey · Zbl 1201.90001 |
| [2] | Alon, N., A note on network reliability, (Aldous, D.; Diaconis, P.; Spencer, J.; Steele, J. M., Discrete Probability and Algorithms. Discrete Probability and Algorithms, IMA Volumes in Mathematics and Its Applications, vol. 72 (1995), Springer-Verlag), 11-14 · Zbl 0830.60086 |
| [3] | Bakker, H.; Dunke, F.; Nickel, S., A structuring review on multi-stage optimization under uncertainty: aligning concepts from theory and practice, Omega (2019) |
| [4] | Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization, Princeton Series in Applied Mathematics (2009), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 1221.90001 |
| [5] | Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Math. Program., Ser. A, 99, 351-376 (2003) · Zbl 1089.90037 |
| [6] | Büsing, C., Recoverable Robustness in Combinatorial Optimization (2011), Technical University of Berlin: Technical University of Berlin Berlin, PhD thesis |
| [7] | Corsten, H.; Hopf, M.; Kasper, B.; Thielen, C., Assortment planning for multiple chain stores, OR Spektrum, 1-38 (2017) |
| [8] | Deineko, V. G.; Woeginger, G. J., Complexity and in-approximability of a selection problem in robust optimization, 4OR, 11, 249-252 (2013) · Zbl 1287.90085 |
| [9] | Dhamdhere, K.; Ravi, R.; Singh, M., On two-stage stochastic minimum spanning trees, (Jünger, M.; Kaibel, V., IPCO 2005. IPCO 2005, Lecture Notes in Computer Science, vol. 3509 (2005), Springer-Verlag), 321-334 · Zbl 1119.90359 |
| [10] | Dolgui, A.; Kovalev, S., Min-max and min-max (relative) regret approaches to representatives selection problem, 4OR, 10, 181-192 (2012) · Zbl 1266.90191 |
| [11] | Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM, 45, 634-652 (1998) · Zbl 1065.68573 |
| [12] | Flaxman, A.; Frieze, A.; Krivelevich, M., On the random 2-stage minimum spanning tree, Random Struct. Algorithms, 28, 24-36 (2006) · Zbl 1089.60010 |
| [13] | Garey, M. R.; Johnson, D. S., Computers and Intractability. A Guide to the Theory of NP-Completeness (1979), W. H. Freeman and Company · Zbl 0411.68039 |
| [14] | Kall, P.; Mayer, J., Stochastic Linear Programming. Models, Theory and Computation (2005), Springer · Zbl 1104.90033 |
| [15] | Kall, P.; Wallace, S. W., Stochastic Programming (1994), John Wiley and Sons · Zbl 0812.90122 |
| [16] | Kasperski, A.; Kurpisz, A.; Zieliński, P., Approximability of the robust representatives selection problem, Oper. Res. Lett., 43, 16-19 (2015) · Zbl 1408.90256 |
| [17] | Kasperski, A.; Zieliński, P., On the approximability of robust spanning problems, Theor. Comput. Sci., 412, 365-374 (2011) · Zbl 1206.90145 |
| [18] | Kasperski, A.; Zieliński, P., Robust recoverable and two-stage selection problems, Discrete Appl. Math., 233, 52-64 (2017) · Zbl 1382.90088 |
| [19] | Kasperski, A.; Zieliński, P., Risk averse single machine scheduling - complexity and approximation, J. Sched., 22, 567-580 (2019) · Zbl 1430.90270 |
| [20] | Katriel, I.; Kenyon-Mathieu, C.; Upfal, E., Commitment under uncertainty: two-stage matching problems, Theor. Comput. Sci., 408, 213-223 (2008) · Zbl 1165.90583 |
| [21] | Magnanti, T. L.; Wolsey, L. A., Optimal trees, (Ball, M. O.; Magnanti, T. L.; Monma, C. L.; Nemhauser, G. L., Network Models. Network Models, Handbook in Operations Research and Management Science, vol. 7 (1995), North-Holland: North-Holland Amsterdam), 503-615 · Zbl 0839.90135 |
| [22] | Mitzenmacher, M.; Upfal, E., Probability and Computing: Randomized Algorithms and Probabilistic Analysis (2005), Cambridge University Press · Zbl 1092.60001 |
| [23] | Pflug, G. C., Some remarks on the value-at-risk and the conditional value-at-risk, (Uryasev, S. P., Probabilistic Constrained Optimization: Methodology and Applications (2000), Kluwer Academic Publishers), 272-281 · Zbl 0994.91031 |
| [24] | Raghavan, P., Probabilistic construction of deterministic algorithms: approximating packing integer programs, J. Comput. Syst. Sci., 37, 130-143 (1988) · Zbl 0659.90066 |
| [25] | Rockafellar, R. T.; Uryasev, S. P., Optimization of conditional value-at-risk, J. Risk, 2, 21-41 (2000) |
| [26] | Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series parallel digraphs, SIAM J. Comput., 11, 298-313 (1982) · Zbl 0478.68065 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
