A multi-parametric programming algorithm for special classes of non-convex multilevel optimization problems
DOI:
https://doi.org/10.11121/ijocta.01.2013.00156Keywords:
Multi-level programming, Multi-parametric programming, Branch-and-bound, ConvexificationAbstract
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 program-ming approach. A branch-and-bound procedure is employed until a pre-specied positive tolerance issatised. Moreover, a ϵ-convergence proof is given for the algorithm.
Downloads
References
Migdalas, A., Pardalos, M.P., and V¨arbrand, P., Multilevel optimization: algorithm, theory and applications. Kluwer Acadamic Publisher, (1992).
Vicente, N.L. and Calamai, H.P., Bilevel and multilevel programming: a bibliography review. Journal of Global Optimization, 5, 1 - 9 (1994). Crossref
Hansen, P., Jaumard, B., and Savard, G., New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientiï¬c and Statistical Computing, 13, 1194 - 1217 (1992). Crossref
Blair, C., The computational complexity of multi-level linear programs. Annals of Operations Research, 34, 13 - 19 (1992). Crossref
Bard, J.F., An investigation of the linear three level programming problem. IEEE Transactions on Systems, Man, and Cybernetics, 14, 711 – 717 (1984). Crossref
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). Crossref
Mersha, A.Y., Dempe S., Feasible direction method for bilevel programming problem. Optimization, 61(5), 597 - 616 (2012). Crossref
Gumus, Z.H., Floudas C.A., Global Optimization of Nonlinear Bilevel Programming Problems. Journal of Global Optimization, 20, 1 - 31 (2001). Crossref
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).
Faisca, 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). Crossref
Faisca, 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). Crossref
Fiacco, V.A., Sensitivity analysis for nonlinear programming using penalty methods. Mathematical Programming, 10, 287 - 311 (1976). Crossref
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). Crossref
Pistikopoulos, N.E., Georgiadis C.M. and Dua V., (Editors) Multiparametric programming: Theory, algorithm, and application. WILEY-VCH Verlag GmbH and Co. KGaA, (2007).
Penginapan Ciawi. (2020). Retrieved 21 May 2020, from http://www.penginapanciawi.my.id/
Al-Khayyal, F.A., Jointly constrained bilinear programs and related problems: an overview. Computers Math. Applic., 19(11), 53 - 62 (1990). Crossref
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). Crossref
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). Crossref
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). Crossref
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
