Abstract
This paper presents a three-stage optimization algorithm for solving two-stage deviation robust decision making problems under uncertainty. The structure of the first-stage problem is a mixed integer linear program and the structure of the second-stage problem is a linear program. Each uncertain model parameter can independently take its value from a real compact interval with unknown probability distribution. The algorithm coordinates three mathematical programming formulations to iteratively solve the overall problem. This paper provides the application of the algorithm on the robust facility location problem and a counterexample illustrating the insufficiency of the solution obtained by considering only a finite number of scenarios generated by the endpoints of all intervals.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic, Dordrecht (1997)
Von Stackelberg, H.: Grundzuge der Theoretischen Volkswirtschaftslehre Stuttgart. Kohlhammer, Berlin (1943)
Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Methods Oper. Res. 23, 769–805 (1998)
Ben-Tal, A., Nemirovski, A.: Robust solutions to uncertain programs. Oper. Res. Lett. 25, 1–13 (1999)
Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88, 411–424 (2000)
Ben-Tal, A., El-Ghaoui, L., Nemirovski, A.: Robust semidefinite programming. In: Saigal, R., Vandenberghe, L., Wolkowicz, H. (eds.) Semidefinite Programming and Applications. Kluwer Academic, Dordrecht (2000)
Averbakh, I.: Minmax regret solutions for minimax optimization problems with uncertainty. Oper. Res. Lett. 27(2), 57–65 (2000)
Averbakh, I.: On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. 90, 263–272 (2001)
Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. Ser. B 98, 49–71 (2003)
Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)
Assavapokee, T., Realff, M., Ammons, J., Hong, I.: Scenario relaxation algorithm for finite scenario based min-max regret and min-max relative regret robust optimization. Comput. Oper. Res. 35(6), (2008)
Bard, J.F., Moore, J.T.: A branch and bound algorithm for the bilevel programming problem. SIAM J. Sci. Stat. Comput. 11(2), 281–292 (1990)
Assavapokee, T.: Semi continuous robust approach for strategic infrastructure planning of reverse production systems. Ph.D. Thesis, Georgia Institute of Technology (2004)
Bard, J.F., Falk, J.E.: An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9(1), 77–100 (1982)
Bard, J.F.: Some properties of bilevel programming problem. J. Optim. Theory Appl. 68(2), 371–378 (1991)
Bard, J.F.: Practical Bilevel Optimization: Algorithms and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic, Dordrecht (1998)
Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13(5), 1194–1217 (1992)
Migdalas, A., Pardalos, P.M., Varbrand, P. (eds.): Multilevel Optimization: Algorithms and Applications. Kluwer Academic, Dordrecht (1997)
Huang, H.X., Pardalos, P.M.: A multivariate partition approach to optimization problems. Cybern. Syst. Anal. 38(2), 265–275 (2002)
Chopra, S., Meindl, P.: Supply Chain Management: Strategy, Planning, and Operations, 2nd edn. Prentice Hall, Upper Saddle River (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by P.M. Pardalos.
This work was supported by the National Science Foundation through Grant DMI-0200162.
Rights and permissions
About this article
Cite this article
Assavapokee, T., Realff, M.J. & Ammons, J.C. Min-Max Regret Robust Optimization Approach on Interval Data Uncertainty. J Optim Theory Appl 137, 297–316 (2008). https://doi.org/10.1007/s10957-007-9334-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9334-6