Abay Molla KASSA, Semu Mitiku KASSA

A multi-parametric programming algorithm for special classes of non-convex multilevel optimization problems

A global solution strategy for multilevel optimization problems with special non-convexityformulation in the objectives of the inner level problems is presented based on branch-and-bound andmulti-parametric programming approach. An algorithm to such problems is proposed by convexifyingthe inner level problem while the variables from upper level problems are considered as parameters.The resulting convex parametric under-estimator problem is solved using multi-parametric programming approach. A branch-and-bound procedure is employed until a pre-specified positive tolerance issatisfied. Moreover, a ?-convergence proof is given for the algorithm.

PDF

___

[1] Migdalas, A., Pardalos, M.P., and V¨arbrand, P., Multilevel optimization: algorithm, theory and applications. Kluwer Acadamic Publisher, (1992).
[2] Vicente, N.L. and Calamai, H.P., Bilevel and multilevel programming: a bibliography review. Journal of Global Optimization, 5, 1 - 9 (1994).
[3] Hansen, P., Jaumard, B., and Savard, G., New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing, 13, 1194 - 1217 (1992).
[4] Blair, C., The computational complexity of multi-level linear programs. Annals of Operations Research, 34, 13 - 19 (1992).
[5] Bard, J.F., An investigation of the linear three level programming problem. IEEE Transactions on Systems, Man, and Cybernetics, 14, 711 - 717 (1984).
[6] Zhang, G., Lu, J., Montero, J., Zeng, Y., Model, solution concept, and Kth-best algorithm for linear trilevel programming. Information Sciences, 180, 481 - 492 (2010).
[7] Mersha, A.Y., Dempe S., Feasible direction method for bilevel programming problem. Optimization, 61(5), 597 - 616 (2012) . [8] G¨um¨us, Z.H., Floudas C.A., Global Optimization of Nonlinear Bilevel Programming Problems. Journal of Global Optimization, 20, 1 - 31 (2001).
[9] Tilahun, S.L., Kassa S.M., and Ong, H.C., A new algorithm for multilevel optimization problems using evolutionary strategy, inspired by natural selection. In: Anthony, A., Ishizuka, M., and Lukose, D., (Eds.): PRICAI 2012, LNAI 7458, Springer-Verlag, Berlin Heidelberg, 577 - 588 (2012).
[10] Fa´ısca, P.N., Dua, V., Rustem, B., Saraiva, M.P., Pistikopoulos, N.E., Parametric global optimisation for bilevel programming. Journal of Global Optimization, 38, 609 - 623 (2006).
[11] Fa´ısca, P.N., Saraiva, M.P., Rustem, B., Pistikopoulos, N.E., A multiparametric programming approach for multilevel hierarchical and decentralized optimization problems. Computational Management Science, 6, 377 - 397 (2009).
[12] Fiacco, V.A., Sensitivity analysis for nonlinear programming using penalty methods. Mathematical Programming, 10, 287 - 311 (1976).
[13] Dua, V., Pistikopoulos, N.E., An algorithm for the solution of multiparametric mixed integer linear programming problems. Annals of Operations Research, 99, 123 - 139 (2001).
[14] Pistikopoulos, N.E., Georgiadis C.M. and Dua V., (Editors) Multiparametric programming: Theory, algorithm, and application.
15] Fiacco, V.A., Introduction to sensitivity and stability analysis in nonlinear programming. Acadamic press, (1983).
[16] Al-Khayyal, F.A., Jointly constrained bilinear programs and related problems: an overview. Computers Math. Applic., 19(11), 53 - 62 (1990).
[17] Androulakis, P.I., Maranas, D.C., and Floudas, A.C., ?BB: A Global optimization method for general constrained nonconvex problems. Journal of Global Optimization, 7, 1 - 27 (1995).
[18] Adjiman, S.C., Dallwing, S., Floudas, A.C., Neumaier, A., A global optimization method, ?BB, for general twice-defferentiable constrained NLPs - I. Theoretical advances. Computers and Chemical Engineering, 22, 1137 - 1158 (1998).
[19] Adjiman, S.C., Androulakis, P.I., Floudas, A.C., A global optimization method, ?BB, for general twice-defferentiable constrained NLPs - II. Implementaion and Computational results. Computers and Chemical Engineering, 22, 1159 - 1179 (1998).