×

zbMATH — the first resource for mathematics

Solving two-stage robust optimization problems using a column-and-constraint generation method. (English) Zbl 1286.90143
Summary: We present a column-and-constraint generation algorithm to solve two-stage robust optimization problems. Compared with existing Benders-style cutting plane methods, the column-and-constraint generation algorithm is a general procedure with a unified approach to deal with optimality and feasibility. A computational study on a two-stage robust location-transportation problem shows that it performs an order of magnitude faster.

MSC:
90C30 Nonlinear programming
90C31 Sensitivity, stability, parametric optimization
90B06 Transportation, logistics and supply chain management
PDF BibTeX Cite
Full Text: DOI
References:
[1] Atamturk, A.; Zhang, M., Two-stage robust network flow and design under demand uncertainty, Operations Research, 55, 4, 662-673, (2007) · Zbl 1167.90409
[2] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252, (1962) · Zbl 0109.38302
[3] Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Mathematical Programming, 99, 2, 351-376, (2004) · Zbl 1089.90037
[4] Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Mathematics of Operations Research, 23, 4, 769-805, (1998) · Zbl 0977.90052
[5] Ben-Tal, A.; Nemirovski, A., Robust solutions of uncertain linear programs, Operations Research Letters, 25, 1, 1-14, (1999) · Zbl 0941.90053
[6] Ben-Tal, A.; Nemirovski, A., Robust solutions of linear programming problems contaminated with uncertain data, Mathematical Programming, 88, 3, 411-424, (2000) · Zbl 0964.90025
[7] Bertsimas, D.; Brown, D. B.; Caramanis, C., Theory and applications of robust optimization, SIAM Review, 53, 3, 464-501, (2011) · Zbl 1233.90259
[8] Bertsimas, D.; Litvinov, E.; Sun, X. A.; Zhao, Jinye; Zheng, Tongxin, Adaptive robust optimization for the security constrained unit commitment problem, IEEE Transactions on Power Systems, 28, 1, 52-63, (2013)
[9] Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Mathematical Programming, 98, 1, 49-71, (2003) · Zbl 1082.90067
[10] Bertsimas, D.; Sim, M., The price of robustness, Operations Research, 52, 1, 35-53, (2004) · Zbl 1165.90565
[11] Electronic companion—solving two-stage robust optimization problems using a column-and-constraint generation method. http://imse.eng.usf.edu/faculty/bzeng/MOChA_group/Index.htm.
[12] El Ghaoui, L.; Oustry, F.; Lebret, H., Robust solutions to uncertain semidefinite programs, SIAM Journal on Optimization, 9, 33-52, (1998) · Zbl 0960.93007
[13] Gabrel, V.; Lacroix, M.; Murat, C.; Remli, N., Robust location transportation problems under uncertain demands, Discrete Applied Mathematics, (2013), in press. Available online · Zbl 1331.90096
[14] Geoffrion, A. M., Generalized benders decomposition, Journal of Optimization Theory and Applications, 10, 4, 237-260, (1972) · Zbl 0229.90024
[15] R. Jiang, M. Zhang, G. Li, Y. Guan, Benders decomposition for the two-stage security constrained robust unit commitment problem, Technical Report, University of Florida, 2011. Available in Optimization-Online.
[16] Ordonez, F.; Zhao, J., Robust capacity expansion of network flows, Networks, 50, 2, 136-145, (2007) · Zbl 1144.90325
[17] Takeda, A.; Taguchi, S.; Tutuncu, R. H., Adjustable robust optimization models for a nonlinear two-period system, Journal of Optimization Theory and Applications, 136, 2, 275-295, (2008) · Zbl 1146.90075
[18] T.L. Terry, Robust linear optimization with recourse: solution methods and other properties. Ph.D. Thesis, University of Michigan, 2009.
[19] A. Thiele, T. Terry, M. Epelman, Robust linear optimization with recourse, Technical Report, 2010. Available in Optimization-Online.
[20] L. Zhao, B. Zeng, An exact algorithm for two-stage robust optimization with mixed integer recourse problems, Technical Report, University of South Florida, 2012. Available in Optimization-Online.
[21] Long Zhao, Bo Zeng, Robust unit commitment problem with demand response and wind energy. in: Proceedings of Power and Energy Society General Meeting, 2012 IEEE, 2012, pp. 1-8.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.