Skip to main content
Springer Nature Link
Log in

Algorithm Engineering in Robust Optimization

  • Chapter
  • First Online:
Algorithm Engineering

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9220))

  • 6025 Accesses

Abstract

Robust optimization is a young and emerging field of research having received a considerable increase of interest over the last decade. In this paper, we argue that the algorithm engineering methodology fits very well to the field of robust optimization and yields a rewarding new perspective on both the current state of research and open research directions.

To this end we go through the algorithm engineering cycle of design and analysis of concepts, development and implementation of algorithms, and theoretical and experimental evaluation. We show that many ideas of algorithm engineering have already been applied in publications on robust optimization. Most work on robust optimization is devoted to analysis of the concepts and the development of algorithms, some papers deal with the evaluation of a particular concept in case studies, and work on comparison of concepts just starts. What is still a drawback in many papers on robustness is the missing link to include the results of the experiments again in the design.

Partially supported by grant SCHO 1140/3-2 within the DFG programme Algorithm Engineering.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 52.74
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://www-03.ibm.com/software/products/en/ibmilogcpleoptistud.

  2. 2.

    http://www.fico.com/en/products/fico-xpress-optimization-suite.

  3. 3.

    http://www.gurobi.com/.

  4. 4.

    http://www.mathworks.com/products/matlab/.

  5. 5.

    http://www.math.nus.edu.sg/~mattohkc/sdpt3.html.

  6. 6.

    Number of items for finite, strict knapsack is estimated with the pegging test from [122].

References

  1. Adasme, P., Lisser, A., Soto, I.: Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme. Comput. Oper. Res. 38(10), 1377–1399 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  2. Agra, A., Christiansen, M., Figueiredo, R., Hvattum, L.M., Poss, M., Requejo, C.: The robust vehicle routing problem with time windows. Comput. Oper. Res. 40(3), 856–866 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Aissi, H., Bazgan, C., Vanderpooten, D.: Approximation of min–max and min–max regret versions of some combinatorial optimization problems. Eur. J. Oper. Res. 179(2), 281–290 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  4. Aissi, H., Bazgan, C., Vanderpooten, D.: Min–max and min–max regret versions of combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197(2), 427–438 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Alem, D.J., Morabito, R.: Production planning in furniture settings via robust optimization. Comput. Oper. Res. 39(2), 139–150 (2012)

    Article  MATH  Google Scholar 

  6. Arrival project under contract no. FP6-021235-2. http://arrival.cti.gr/index.php/Main/HomePage

  7. Atamtürk, A.: Strong formulations of robust mixed 0–1 programming. Math. Program. 108(2), 235–250 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Averbakh, I.: The minmax regret permutation flow-shop problem with two jobs. Eur. J. Oper. Res. 169(3), 761–766 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Averbakh, I., Berman, O.: Algorithms for the robust 1-center problem on a tree. Eur. J. Oper. Res. 123(2), 292–302 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  10. Beck, A., Ben-Tal, A.: Duality in robust optimization: primal worst equals dual best. Oper. Res. Lett. 37(1), 1–6 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Ben-Tal, A., Bertsimas, D., Brown, D.B.: A soft robust model for optimization under ambiguity. Oper. Res. 58(4–Part–2), 1220–1234 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Ben-Tal, A., Boyd, S., Nemirovski, A.: Extending scope of robust optimization: comprehensive robust counterparts of uncertain problems. Math. Program. 107(1–2), 63–89 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ben-Tal, A., Chung, B.D., Mandala, S.R., Yao, T.: Robust optimization for emergency logistics planning: risk mitigation in humanitarian relief supply chains. Transp. Res. Part B: Methodol. 45(8), 1177–1189 (2011)

    Article  Google Scholar 

  14. Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)

    Book  MATH  Google Scholar 

  15. Ben-Tal, A., Golany, B., Shtern, S.: Robust multi-echelon multi-period inventory control. Eur. J. Oper. Res. 199(3), 922–935 (2009)

    Article  MATH  Google Scholar 

  16. Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Program. A 99, 351–376 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  17. Ben-Tal, A., den Hertog, D., Vial, J.P.: Deriving robust counterparts of nonlinear uncertain inequalities. Math. Program. 149(1), 265–299 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  18. Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769–805 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  19. Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25, 1–13 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. A 88, 411–424 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  21. Berman, O., Wang, J.: The minmax regret gradual covering location problem on a network with incomplete information of demand weights. Eur. J. Oper. Res. 208(3), 233–238 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  22. Bertsimas, D., Brown, D., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464–501 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  23. Bertsimas, D., Caramanis, C.: Finite adaptability in multistage linear optimization. IEEE Trans. Autom. Control 55(12), 2751–2766 (2010)

    Article  MathSciNet  Google Scholar 

  24. Bertsimas, D., Goyal, V.: On the power of robust solutions in two-stage stochastic and adaptive optimization problems. Math. Oper. Res. 35(2), 284–305 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  25. Bertsimas, D., Goyal, V., Sun, X.A.: A geometric characterization of the power of finite adaptability in multistage stochastic and adaptive optimization. Math. Oper. Res. 36(1), 24–54 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  26. Bertsimas, D., Pachamanova, D.: Robust multiperiod portfolio management in the presence of transaction costs. Comput. Oper. Res. 35(1), 3–17 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  27. Bertsimas, D., Pachamanova, D., Sim, M.: Robust linear optimization under general norms. Oper. Res. Lett. 32(6), 510–516 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  28. Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  29. Bertsimas, D., Thiele, A.: A robust optimization approach to inventory theory. Oper. Res. 54(1), 150–168 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  30. Bohle, C., Maturana, S., Vera, J.: A robust optimization approach to wine grape harvesting scheduling. Eur. J. Oper. Res. 200(1), 245–252 (2010)

    Article  MATH  Google Scholar 

  31. Bouman, P.C., Akker, J.M., Hoogeveen, J.A.: Recoverable robustness by column generation. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 215–226. Springer, Heidelberg (2011). doi:10.1007/978-3-642-23719-5_19

    Chapter  Google Scholar 

  32. Bruns, F., Goerigk, M., Knust, S., Schöbel, A.: Robust load planning of trains in intermodal transportation. OR Spectr. 36(3), 631–668 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  33. Bürger, M., Notarstefano, G., Allgöwer, F.: A polyhedral approximation framework for convex and robust distributed optimization. IEEE Trans. Autom. Control 59(2), 384–395 (2014)

    Article  MathSciNet  Google Scholar 

  34. Büsing, C., Koster, A.M.C.A., Kutschka, M.: Recoverable robust knapsacks: the discrete scenario case. Optim. Lett. 5(3), 379–392 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  35. Büsing, C., Koster, A., Kutschka, M.: Recoverable robust knapsacks: \(\varGamma \)-scenarios. In: Pahl, J., Reiners, T., Voß, S. (eds.) Network Optimization. Lecture Notes in Computer Science, vol. 6701, pp. 583–588. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  36. Cacchiani, V., Caprara, A., Galli, L., Kroon, L., Maroti, G., Toth, P.: Railway rolling stock planning: robustness against large disruptions. Transp. Sci. 46(2), 217–232 (2012)

    Article  MATH  Google Scholar 

  37. Calafiore, G., Campi, M.: Uncertain convex programs: randomized solutions and confidence levels. Math. Program. 102(1), 25–46 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  38. Calafiore, G.C.: Random convex programs. SIAM J. Optim. 20(6), 3427–3464 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  39. Calafiore, G., Campi, M.: The scenario approach to robust control design. IEEE Trans. Autom. Control 51(5), 742–753 (2006)

    Article  MathSciNet  Google Scholar 

  40. Campi, M.C., Garatti, S.: The exact feasibility of randomized solutions of uncertain convex programs. SIAM J. Optim. 19(3), 1211–1230 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  41. Catanzaro, D., Labbé, M., Salazar-Neumann, M.: Reduction approaches for robust shortest path problems. Comput. Oper. Res. 38(11), 1610–1619 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  42. Chassein, A.B., Goerigk, M.: A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem. Eur. J. Oper. Res. 244(3), 739–747 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  43. Cicerone, S., D’Angelo, G., Stefano, G.D., Frigioni, D., Navarra, A.: Robust algorithms and price of robustness in shunting problems. In: Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2007) (2007)

    Google Scholar 

  44. Cicerone, S., D’Angelo, G., Stefano, G., Frigioni, D., Navarra, A., Schachtebeck, M., Schöbel, A.: Recoverable robustness in shunting and timetabling. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 28–60. Springer, Heidelberg (2009). doi:10.1007/978-3-642-05465-5_2

    Chapter  Google Scholar 

  45. Conde, E.: Minmax regret location–allocation problem on a network under uncertainty. Eur. J. Oper. Res. 179(3), 1025–1039 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  46. Conde, E.: A minmax regret approach to the critical path method with task interval times. Eur. J. Oper. Res. 197(1), 235–242 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  47. Conde, E.: On a constant factor approximation for minmax regret problems using a symmetry point scenario. Eur. J. Oper. Res. 219(2), 452–457 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  48. Conde, E., Candia, A.: Minimax regret spanning arborescences under uncertain costs. Eur. J. Oper. Res. 182(2), 561–577 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  49. D’Angelo, G., Di Stefano, G., Navarra, A.: Recoverable-robust timetables for trains on single-line corridors. In: Proceedings of the 3rd International Seminar on Railway Operations Modelling and Analysis - Engineering and Optimisation Approaches (RailZurich 2009) (2009)

    Google Scholar 

  50. Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering route planning algorithms. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science, vol. 5515, pp. 117–139. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  51. Dhamdhere, K., Goyal, V., Ravi, R., Singh, M.: How to pay, come what may: approximation algorithms for demand-robust covering problems. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 367–376. IEEE (2005)

    Google Scholar 

  52. Eggenberg, N.: Combining robustness and recovery for airline schedules. Ph.D. thesis, EPFL (2009)

    Google Scholar 

  53. Eggenberg, N., Salani, M., Bierlaire, M.: Uncertainty feature optimization: an implicit paradigm for problems with noisy data. Networks 57(3), 270–284 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  54. Erera, A., Morales, J., Svalesbergh, M.: Robust optimization for empty repositioning problems. Oper. Res. 57(2), 468–483 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  55. Falk, J.E.: Exact solutions of inexact linear programs. Oper. Res. 24(4), 783–787 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  56. de Farias, J.R., Zhao, H., Zhao, M.: A family of inequalities valid for the robust single machine scheduling polyhedron. Comput. Oper. Res. 37(9), 1610–1614 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  57. Feige, U., Jain, K., Mahdian, M., Mirrokni, V.: Robust combinatorial optimization with exponential scenarios. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 439–453. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72792-7_33

    Chapter  Google Scholar 

  58. Fischetti, M., Monaci, M.: Light robustness. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 61–84. Springer, Heidelberg (2009). doi:10.1007/978-3-642-05465-5_3

    Chapter  Google Scholar 

  59. Fischetti, M., Monaci, M.: Cutting plane versus compact formulations for uncertain (integer) linear programs. Math. Program. Comput. 4(3), 239–273 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  60. Fischetti, M., Salvagnin, D., Zanette, A.: Fast approaches to improve the robustness of a railway timetable. Transp. Sci. 43, 321–335 (2009)

    Article  Google Scholar 

  61. Fujisaki, Y., Wada, T.: Sequential randomized algorithms for robust optimization. In: Proceedings of the 46th IEEE Conference on Decision and Control, pp. 6190–6195 (2007)

    Google Scholar 

  62. Fujisaki, Y., Wada, T.: Robust optimization via probabilistic cutting plane technique. In: Proceedings of the 40th ISCIE International Symposium on Stochastic Systems Theory and its Applications, pp. 137–142 (2009)

    Google Scholar 

  63. Fujisaki, Y., Wada, T.: Robust optimization via randomized algorithms. In: ICCAS-SICE 2009, pp. 1226–1229 (2009)

    Google Scholar 

  64. Ghaoui, L.E., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18, 1034–1064 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  65. Goerigk, M.: Algorithms and concepts for robust optimization. Ph.D. thesis, Georg-August Universität Göttingen (2012)

    Google Scholar 

  66. Goerigk, M.: ROPI homepage (2013). http://optimierung.mathematik.uni-kl.de/~goerigk/ropi/

  67. Goerigk, M.: A note on upper bounds to the robust knapsack problem with discrete scenarios. Ann. Oper. Res. 223(1), 461–469 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  68. Goerigk, M.: ROPI - a robust optimization programming interface for C++. Optim. Methods Softw. 29(6), 1261–1280 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  69. Goerigk, M., Deghdak, K., T’Kindt, V.: A two-stage robustness approach to evacuation planning with buses. Transp. Res. Part B: Methodol. 78, 66–82 (2015)

    Article  Google Scholar 

  70. Goerigk, M., Heße, S., Müller-Hannemann, M., Schmidt, M., Schöbel, A.: Recoverable robust timetable information. In: Frigioni, D., Stiller, S. (eds.) 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. OpenAccess Series in Informatics (OASIcs), vol. 33, pp. 1–14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2013)

    Google Scholar 

  71. Goerigk, M., Knoth, M., Müller-Hannemann, M., Schmidt, M., Schöbel, A.: The price of robustness in timetable information. In: Caprara, A., Kontogiannis, S. (eds.) 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 76–87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2011)

    Google Scholar 

  72. Goerigk, M., Schmidt, M., Schöbel, A., Knoth, M., Müller-Hannemann, M.: The price of strict and light robustness in timetable information. Transp. Sci. 48(2), 225–242 (2014)

    Article  MATH  Google Scholar 

  73. Goerigk, M., Schöbel, A.: An empirical analysis of robustness concepts for timetabling. In: Erlebach, T., Lübbecke, M. (eds.) 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010). OpenAccess Series in Informatics (OASIcs), vol. 14, pp. 100–113. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2010)

    Google Scholar 

  74. Goerigk, M., Schöbel, A.: A scenario-based approach for robust linear optimization. In: Marchetti-Spaccamela, A., Segal, M. (eds.) TAPAS 2011. LNCS, vol. 6595, pp. 139–150. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19754-3_15

    Chapter  Google Scholar 

  75. Goerigk, M., Schöbel, A.: Recovery-to-optimality: a new two-stage approach to robustness with an application to aperiodic timetabling. Comput. Oper. Res. 52(Part A), 1–15 (2014)

    Article  MathSciNet  Google Scholar 

  76. Goetzmann, K.S., Stiller, S., Telha, C.: Optimization over integers with robustness in cost and few constraints. In: Solis-Oba, R., Persiano, G. (eds.) Approximation and Online Algorithms (WAOA 2011). Lecture Notes in Computer Science, vol. 7164, pp. 89–101. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  77. Goh, J., Sim, M.: Robust optimization made easy with ROME. Oper. Res. 59(4), 973–985 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  78. Golovin, D., Goyal, V., Polishchuk, V., Ravi, R., Sysikaski, M.: Improved approximations for two-stage min-cut and shortest path problems under uncertainty. Math. Program. 149(1), 167–194 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  79. Iida, H.: A note on the max-min 0–1 knapsack problem. J. Comb. Optim. 3(1), 89–94 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  80. Inuiguchi, M., Sakawa, M.: Minimax regret solution to linear programming problems with an interval objective function. Eur. J. Oper. Res. 86(3), 526–536 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  81. Jenkins, L.: Selecting scenarios for environmental disaster planning. Eur. J. Oper. Res. 121(2), 275–286 (2000)

    Article  MATH  Google Scholar 

  82. Jeyakumar, V., Li, G., Srisatkunarajah, S.: Strong duality for robust minimax fractional programming problems. Eur. J. Oper. Res. 228(2), 331–336 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  83. Kalai, R., Lamboray, C., Vanderpooten, D.: Lexicographic \(\alpha \)-robustness: an alternative to min–max criteria. Eur. J. Oper. Res. 220(3), 722–728 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  84. Kasperski, A., Kurpisz, A., Zieliński, P.: Approximating a two-machine flow shop scheduling under discrete scenario uncertainty. Eur. J. Oper. Res. 217(1), 36–43 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  85. Kasperski, A., Makuchowski, M., Zieliński, P.: A tabu search algorithm for the minmax regret minimum spanning tree problem with interval data. J. Heuristics 18(4), 593–625 (2012)

    Article  Google Scholar 

  86. Kasperski, A., Zieliński, P.: An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett. 97(5), 177–180 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  87. Kasperski, A., Zieliński, P.: Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights. Eur. J. Oper. Res. 200(3), 680–687 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  88. Khandekar, R., Kortsarz, G., Mirrokni, V., Salavatipour, M.R.: Two-stage robust network design with exponential scenarios. Algorithmica 65(2), 391–408 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  89. Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, Boston (1997)

    Book  MATH  Google Scholar 

  90. Liebchen, C., Lübbecke, M., Möhring, R., Stiller, S.: The concept of recoverable robustness, linear programming recovery, and railway applications. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 1–27. Springer, Heidelberg (2009). doi:10.1007/978-3-642-05465-5_1

    Chapter  Google Scholar 

  91. Lin, J., Ng, T.S.: Robust multi-market newsvendor models with interval demand data. Eur. J. Oper. Res. 212(2), 361–373 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  92. Löfberg, J.: Automatic robust convex programming. Optim. Methods Softw. 27(1), 115–129 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  93. López, M., Still, G.: Semi-infinite programming. Eur. J. Oper. Res. 180(2), 491–518 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  94. Mani, M., Sing, A.K., Orshansky, M.: Joint design-time and post-silicon minimization of parametric yield loss using adjustable robust optimization. In: Proceedings of the 2006 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2006, pp. 19–26. ACM, New York (2006)

    Google Scholar 

  95. Mausser, H.E., Laguna, M.: A heuristic to minimax absolute regret for linear programs with interval objective function coefficients. Eur. J. Oper. Res. 117(1), 157–174 (1999)

    Article  MATH  Google Scholar 

  96. Mausser, H., Laguna, M.: A new mixed integer formulation for the maximum regret problem. Int. Trans. Oper. Res. 5(5), 389–403 (1998)

    Article  Google Scholar 

  97. Monaci, M., Pferschy, U.: On the robust knapsack problem. SIAM J. Optim. 23(4), 1956–1982 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  98. Monaci, M., Pferschy, U., Serafini, P.: Exact solution of the robust knapsack problem. Comput. Oper. Res. 40(11), 2625–2631 (2013)

    Article  MathSciNet  Google Scholar 

  99. Montemanni, R.: A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 174(3), 1479–1490 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  100. Montemanni, R., Gambardella, L.: An exact algorithm for the robust shortest path problem with interval data. Comput. Oper. Res. 31(10), 1667–1680 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  101. Montemanni, R., Gambardella, L.: A branch and bound algorithm for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 161(3), 771–779 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  102. Müller-Hannemann, M., Schirra, S. (eds.): Algorithm Engineering. LNCS, vol. 5971. Springer, Heidelberg (2010)

    Google Scholar 

  103. Mulvey, J.M., Vanderbei, R.J., Zenios, S.A.: Robust optimization of large-scale systems. Oper. Res. 43(2), 264–281 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  104. Mutapcic, A., Boyd, S.: Cutting-set methods for robust convex optimization with pessimizing oracles. Optim. Methods Softw. 24(3), 381–406 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  105. Ng, T.S., Sun, Y., Fowler, J.: Semiconductor lot allocation using robust optimization. Eur. J. Oper. Res. 205(3), 557–570 (2010)

    Article  MATH  Google Scholar 

  106. Nikulin, Y.: Simulated annealing algorithm for the robust spanning tree problem. J. Heuristics 14(4), 391–402 (2008)

    Article  MATH  Google Scholar 

  107. Ouorou, A.: Tractable approximations to a robust capacity assignment model in telecommunications under demand uncertainty. Comput. Oper. Res. 40(1), 318–327 (2013)

    Article  MathSciNet  Google Scholar 

  108. Paragon Decision Company: AIMMS - The Language Reference, Version 3.12, March 2012

    Google Scholar 

  109. Pereira, J., Averbakh, I.: Exact and heuristic algorithms for the interval data robust assignment problem. Comput. Oper. Res. 38(8), 1153–1163 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  110. Pérez-Galarce, F., Álvarez-Miranda, E., Candia-Véjar, A., Toth, P.: On exact solutions for the minmax regret spanning tree problem. Comput. Oper. Res. 47, 114–122 (2014)

    Article  MathSciNet  Google Scholar 

  111. Reemtsen, R.: Some outer approximation methods for semi-infinite optimization problems. J. Comput. Appl. Math. 53(1), 87–108 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  112. Roy, B.: Robustness in operational research and decision aiding: a multi-faceted issue. Eur. J. Oper. Res. 200(3), 629–638 (2010)

    Article  MATH  Google Scholar 

  113. Sanders, P.: Algorithm engineering – an attempt at a definition. In: Albers, S., Alt, H., Näher, S. (eds.) Efficient Algorithms. LNCS, vol. 5760, pp. 321–340. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03456-5_22

    Chapter  Google Scholar 

  114. Sbihi, A.: A cooperative local search-based algorithm for the multiple-scenario max–min knapsack problem. Eur. J. Oper. Res. 202(2), 339–346 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  115. Schöbel, A.: Generalized light robustness and the trade-off between robustness and nominal quality. Math. Methods Oper. Res. 80(2), 161–191 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  116. Siddiqui, S., Azarm, S., Gabriel, S.: A modified Benders decomposition method for efficient robust optimization under interval uncertainty. Struct. Multidiscip. Optim. 44(2), 259–275 (2011)

    Article  Google Scholar 

  117. Song, X., Lewis, R., Thompson, J., Wu, Y.: An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem. Comput. Oper. Res. 39(9), 1988–2000 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  118. Soyster, A.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21, 1154–1157 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  119. Stiller, S.: Extending concepts of reliability. Network creation games, real-time scheduling, and robust optimization. Ph.D. thesis, TU Berlin (2008)

    Google Scholar 

  120. Suzuki, S., Kuroiwa, D., Lee, G.M.: Surrogate duality for robust optimization. Eur. J. Oper. Res. 231(2), 257–262 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  121. Takeda, A., Taguchi, S., Tütüncü, R.: Adjustable robust optimization models for a nonlinear two-period system. J. Optim. Theory Appl. 136, 275–295 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  122. Taniguchi, F., Yamada, T., Kataoka, S.: Heuristic and exact algorithms for the max–min optimization of the multi-scenario knapsack problem. Comput. Oper. Res. 35(6), 2034–2048 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  123. Thuente, D.J.: Duality theory for generalized linear programs with computational methods. Oper. Res. 28(4), 1005–1011 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  124. Velarde, J.L.G., Martí, R.: Adaptive memory programing for the robust capacitated international sourcing problem. Comput. Oper. Res. 35(3), 797–806 (2008)

    Article  MATH  Google Scholar 

  125. Xu, J., Johnson, M.P., Fischbeck, P.S., Small, M.J., VanBriesen, J.M.: Robust placement of sensors in dynamic water distribution systems. Eur. J. Oper. Res. 202(3), 707–716 (2010)

    Article  MATH  Google Scholar 

  126. Yaman, H., Karaşan, O.E., Pınar, M.Ç.: The robust spanning tree problem with interval data. Oper. Res. Lett. 29(1), 31–40 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  127. Yin, Y., Madanat, S.M., Lu, X.Y.: Robust improvement schemes for road networks under demand uncertainty. Eur. J. Oper. Res. 198(2), 470–479 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  128. Zanjani, M.K., Ait-Kadi, D., Nourelfath, M.: Robust production planning in a manufacturing environment with random yield: a case in sawmill production planning. Eur. J. Oper. Res. 201(3), 882–891 (2010)

    Article  MATH  Google Scholar 

  129. Zieliński, P.: The computational complexity of the relative robust shortest path problem with interval data. Eur. J. Oper. Res. 158(3), 570–576 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Management School, Lancaster University, Lancaster, LA1 4YX, United Kingdom

    Marc Goerigk

  2. Institute of Numerical and Applied Mathematics, University of Göttingen, Lotzestraße 16-18, 37083, Göttingen, Germany

    Anita Schöbel

Authors
  1. Marc Goerigk
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anita Schöbel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marc Goerigk .

Editor information

Editors and Affiliations

  1. Kiel University , Kiel, Germany

    Lasse Kliemann

  2. Karlsruhe Institute of Technology , Karlsruhe, Germany

    Peter Sanders

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing AG

About this chapter

Cite this chapter

Goerigk, M., Schöbel, A. (2016). Algorithm Engineering in Robust Optimization. In: Kliemann, L., Sanders, P. (eds) Algorithm Engineering. Lecture Notes in Computer Science(), vol 9220. Springer, Cham. https://doi.org/10.1007/978-3-319-49487-6_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-49487-6_8

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-49486-9

  • Online ISBN: 978-3-319-49487-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation