K-Adaptability in Two-Stage Robust Binary Programming

References

• Ahmed S (2013) A scenario decomposition algorithm for 0-1 stochastic programs. Oper. Res. Lett. 41(6):565–569.Crossref, Google Scholar
• Alonso-Ayuso A, Escudero LF, Ortuño MT (2003) BFC, a branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs. Eur. J. Oper. Res. 151(3):503–519.Crossref, Google Scholar
• Anderson BDO, Moore JB (1990) Optimal Control: Linear Quadratic Methods (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming A 99(2):351–376.Crossref, Google Scholar
• Bertsimas D, Caramanis C (2007) Adaptability via sampling. Proc. 46th IEEE Conf. Decision and Control (IEEE, Piscataway, NJ),4717–4722.Crossref, Google Scholar
• Bertsimas D, Caramanis C (2010) Finite adaptibility in multistage linear optimization. IEEE Trans. Automatic Control 55(12):2751–2766.Crossref, Google Scholar
• Bertsimas D, Georghiou A (2013) Design of near optimal decision rules in multistage adaptive mixed-integer optimization. Oper. Res., ePub ahead of print April 15, http://dx.doi.org/10.1287/opre.2015.1365.Google Scholar
• Bertsimas D, Georghiou A (2014) Binary decision rules for multistage adaptive mixed-integer optimization. Available on Optimization Online.Google Scholar
• Bertsimas D, Goyal V (2010) On the power of robust solutions in two-stage stochastic and adaptive optimization problems. Math. Oper. Res. 35(2):284–305.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011a) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D, Goyal V, Sun XA (2011b) A geometric characterization of the power of finite adaptability in multistage stochastic and adaptive optimization. Math. Oper. Res. 36(1):24–54.Link, Google Scholar
• Carøe C, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1–2):37–45.Crossref, Google Scholar
• Carøe CC, Tind J (1998) L-shaped decomposition of two-stage stochastic programs with integer recourse. Math. Programming 83(1–3):451–464.Crossref, Google Scholar
• Chen X, Zhang Y (2009) Uncertain linear programs: Extended affinely adjustable robust counterparts. Oper. Res. 57(6):1469–1482.Link, Google Scholar
• Dhamdhere K, Goyal V, Ravi R, Singh M (2005) How to pay, come what may: Approximation algorithms for demand-robust covering problems. 46th Ann. IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 367–376.Crossref, Google Scholar
• Dye S, Stougie L, Tomasgard A (2003) The stochastic single resource service-provision problem. Naval Res. Logist. 50(8):869–887.Crossref, Google Scholar
• Feige U, Jain K, Mahdian M, Mirrokni V (2007) Robust combinatorial optimization with exponential scenarios. Fischetti M, Williamson DP, eds. Integer Programming and Combinatorial Optimization (Springer, Berlin), 439–453.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, New York).Google Scholar
• Georghiou A, Wiesemann W, Kuhn D (2014) Generalized decision rule approximations for stochastic programming via liftings. Math. Programming A. Forthcoming.Google Scholar
• Goh J, Sim M (2010) Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4):902–917.Link, Google Scholar
• Golovin D, Goyal V, Polishchuk V, Ravi R, Sysikaski M (2015) Improved approximations for two-stage min-cut and shortest path problems under uncertainty. Math. Programming A 149(1–2):167–194.Crossref, Google Scholar
• Gorissen BL, Yanikoglu I, den Hertog D (2015) A practical guide to robust optimization, Omega 53:124–137.Google Scholar
• Gounaris CE, Wiesemann W, Floudas CA (2013) The robust capacitated vehicle routing problem under demand uncertainty. Oper. Res. 61(3):677–693.Link, Google Scholar
• Gupta A, Nagarajan V, Ravi R (2010) Thresholded covering algorithms for robust and max-min optimization. Abramsky S, Gavoille C, Kirchner C, Meyer auf der Heide F, Spirakis PG, eds. Proc. 37th Internat. Colloquium Automata, Languages and Programming (Springer, Berlin), 262–274.Crossref, Google Scholar
• Gupta A, Nagarajan V, Vazirani VV (2013) Thrifty algorithms for multistage robust optimization. Goemans M, Correa J, eds. Integer Programming and Combinatorial Optimization (Springer, Berlin),217–228.Crossref, Google Scholar
• Gupta A, Pál M, Ravi R, Sinha A (2005) What about Wednesday? Approximation algorithms for multistage stochastic optimization. Chekuri C, Jansen K, Rolim JDP, Trevisan L, eds. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 86–98.Crossref, Google Scholar
• Gurobi Optimization, Inc. (2014) Gurobi optimizer reference manual. http://www.gurobi.com.Google Scholar
• Hadjiyiannis MJ, Goulart P, Kuhn D (2011) A scenario approach for measuring the suboptimality of linear decision rules in two-stage robust optimization. Proc. 50th IEEE Conf. Decision and Control (IEEE, Piscataway, NJ), 7386–7391.Google Scholar
• Hillier FS, Lieberman GJ (2009) Introduction to Operations Research (McGraw-Hill).Google Scholar
• Iancu DA, Sharma M, Sviridenko M (2013) Supermodularity and affine policies in dynamic robust optimization. Oper. Res. 61(4):941–956.Link, Google Scholar
• Immorlica N, Karger D, Minkoff M, Mirrokni VS (2004) On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. Proc. Fifteenth Ann. ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 691–700.Google Scholar
• Khandekar R, Kortsarz G, Mirrokni V, Salavatipour MR (2013) Two-stage robust network design with exponential scenarios. Algorithmica 65(2):391–408.Crossref, Google Scholar
• Klein Haneveld WK, Stougie L, van der Vlerk MH (1995) On the convex hull of the simple integer recourse objective function. Ann. Oper. Res. 56(1):209–224.Crossref, Google Scholar
• Klein Haneveld WK, Stougie L, van der Vlerk MH (1996) An algorithm for the construction of convex hulls in simple integer recourse programming. Ann. Oper. Res. 64(1):67–81.Crossref, Google Scholar
• Kuhn D, Wiesemann W, Georghiou A (2011) Primal and dual linear decision rules in stochastic and robust optimization. Math. Programming A 130(1):177–209.Crossref, Google Scholar
• Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Li X, Natarajan K, Teo C-P, Zheng Z (2014) Distributionally robust mixed integer linear programs: Persistency model with applications. Eur. J. Oper. Res. 233(3):459–473.Crossref, Google Scholar
• Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. IEEE Internat. Sympos. Comput. Aided Control Systems Design (IEEE, Piscataway, NJ), 284–289.Crossref, Google Scholar
• Louveaux FV, Schultz R (2003) Stochastic integer programming. Ruszczyński A, Shapiro A, eds. Stochastic Programming, Handbooks in Operations Research and Management Science, Vol. 10, Chap. 4 (Elsevier, Amsterdam), 213–266.Crossref, Google Scholar
• Norkin VI, Ermoliev YM, Ruszczyński A (1998) On optimal allocation of indivisibles under uncertainty. Oper. Res. 46(3):381–395.Link, Google Scholar
• Ravi R, Sinha A (2004) Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Bienstock D, Nemhauser G, eds. Integer Programming and Combinatorial Optimization (Springer, Berlin), 101–115.Crossref, Google Scholar
• Romeijnders W, Stougie L, van der Vlerk MH (2014) Approximation in two-stage stochastic integer programming. Surveys Oper. Res. Management Sci. 19(1):17–33.Crossref, Google Scholar
• Schultz R (2003) Stochastic programming with integer variables. Math. Programming 97(1–2):285–309.Crossref, Google Scholar
• Schultz R, Stougie L, van der Vlerk MH (1998) Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis. Math. Programming 83(1–3):229–252.Crossref, Google Scholar
• Sen S, Higle JL (2005) The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Math. Programming A 104(1):1–20.Crossref, Google Scholar
• Sen S, Sherali HD (2006) Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math. Programming A 106(2):203–223.Crossref, Google Scholar
• Sherali HD, Fraticelli BMP (2002) A modification of Benders’ decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse. J. Global Optim. 22(1–4):319–342.Crossref, Google Scholar
• Shmoys DB, Swamy C (2006) An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6):978–1012.Crossref, Google Scholar
• Spacey SA, Wiesemann W, Kuhn D, Luk W (2012) Robust software partitioning with multiple instantiation. INFORMS J. Comput. 24(3):500–515.Link, Google Scholar
• Srinivasan A (2007) Approximation algorithms for stochastic and risk-averse optimization. Proc. Eighteenth Ann. ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1305–1313.Google Scholar
• Swamy C (2011) Risk-averse stochastic optimization: Probabilistically-constrained models and algorithms for black-box distributions. Proc. Twenty-Second Ann. ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1627–1646.Crossref, Google Scholar
• Swamy C, Shmoys D (2012) Sampling-based approximation algorithms for multistage stochastic optimization. SIAM J. Comput. 41(4):975–1004.Crossref, Google Scholar
• van der Vlerk MH (1996–2007) Stochastic integer programming bibliography. http://www.eco.rug.nl/mally/spbib.html.Google Scholar
• Vayanos P, Kuhn D, Rustem B (2011) Decision rules for information discovery in multi-stage stochastic programming. Proc. 50th IEEE Conf. Decision and Control Eur. Control Conf. (IEEE, Piscataway, NJ), 7368–7373.Crossref, Google Scholar