Skip to main content
SpringerLink
Log in

Multi-parametric global optimization approach for tri-level mixed-integer linear optimization problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this work, we present a novel algorithm for the global solution of tri-level mixed-integer linear optimization problems containing both integer and continuous variables at all three optimization levels. Based on multi-parametric theory and our earlier results for bi-level programming problems, the main idea of the algorithm is to recast the lower levels of the tri-level optimization problem as multi-parametric programming problems, in which the optimization variables (continuous and integer) of all the upper level problems, are considered as parameters at the lower levels. The resulting parametric solutions are then substituted into the corresponding higher-level problems sequentially. The algorithm is illustrated through numerical examples, along with implementation and computational studies.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Alguacil, N., Delgadillo, A., Arroyo, J.: A trilevel programming approach for electric grid defense planning. Comput. Oper. Res. 41(1), 282–290 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. Anandalingam, G.: A mathematical programming model of decentralized multi-level systems. J. Oper. Res. Soc. 39(11), 1021–1033 (1988)

    Article  MATH  Google Scholar 

  3. Avraamidou, S., Diangelakis, N.A., Pistikopoulos, E.N.: Mixed integer bilevel optimization through multi-parametric programming. In: Foundations of Computer Aided Process Operations / Chemical Process Control 2017 (2017) http://folk.ntnu.no/skoge/prost/proceedings/focapo-cpc-2017/FOCAPO-CPC%202017%20Contributed%20Papers/73_FOCAPO_Contributed.pdf

  4. Bard, J.: An investigation of the linear three level programming problem. IEEE Trans. Syst. Man Cybern. 14(5), 711–717 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  5. Blair, C.: The computational complexity of multi-level linear programs. Ann. Oper. Res. 34(1), 13–19 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  6. Brown, G., Carlyle, M., Salmern, J., Wood, K.: Defending critical infrastructure. Interfaces 36(6), 530–544 (2006)

    Article  Google Scholar 

  7. Chen, B., Wang, J., Wang, L., He, Y., Wang, Z.: Robust optimization for transmission expansion planning: minimax cost vs. minimax regret. IEEE Trans. Power Syst. 29(6), 3069–3077 (2014)

    Article  Google Scholar 

  8. Dempe, S., Kalashnikov, V., Rios-Mercado, R.Z.: Discrete bilevel programming: application to a natural gas cash-out problem. Eur. J. Oper. Res. 166(2), 469–488 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dempe, S., Mordukhovich, B., Zemkoho, A.: Necessary optimality conditions in pessimistic bilevel programming. Optimization 63(4), 505–533 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Faisca, N.P., Dua, V., Rustem, B., Saraiva, P.M., Pistikopoulos, E.N.: Parametric global optimisation for bilevel programming. J. Glob. Optim. 38(4), 609–623 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Faisca, N.P., Saraiva, P.M., Rustem, B., Pistikopoulos, E.N.: A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems. CMS 6, 377–397 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Floudas, C.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, Oxford (1995)

    MATH  Google Scholar 

  13. Gal, T., Nedoma, J.: Multiparametric linear programming. Manag. Sci. 18(7), 406–422 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  14. Han, J., Zhang, G., Hu, Y., Lu, J.: A solution to bi/tri-level programming problems using particle swarm optimization. Inf. Sci. 370–371, 519–537 (2016)

    Article  Google Scholar 

  15. 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)

    Article  MathSciNet  MATH  Google Scholar 

  16. Jones, C., Kerrigan, E., Maciejowski, J.: Lexicographic perturbation for multiparametric linear programming with applications to control. Automatica 43(10), 1808–1816 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  17. Lai, Y.J.: Hierarchical optimization: a satisfactory solution. Fuzzy Sets Syst. 77(3), 321–335 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  18. Moore, J.T., Bard, J.F.: The mixed integer linear bilevel programming problem. Oper. Res. 38(5), 911–921 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  19. Moreira, A., Street, A., Arroyo, J.: An adjustable robust optimization approach for contingency-constrained transmission expansion planning. IEEE Trans. Power Syst. 30(4), 2013–2022 (2015)

    Article  Google Scholar 

  20. Ning, C., You, F.: Data-driven adaptive nested robust optimization: General modeling framework and efficient computational algorithm for decision making under uncertainty. AIChE J (2017). https://doi.org/10.1002/aic.15717

    Article  Google Scholar 

  21. Oberdieck, R., Diangelakis, N., Avraamidou, S., Pistikopoulos, E.: On unbounded and binary parameters in multi-parametric programming: applications to mixed-integer bilevel optimization and duality theory. J. Glob. Optim. 69, 587–606 (2016a)

    Article  MathSciNet  MATH  Google Scholar 

  22. Oberdieck, R., Wittmann-Hohlbein, M., Pistikopoulos, E.: A branch and bound method for the solution of multiparametric mixed integer linear programming problems. J. Glob. Optim. 59(2–3), 527–543 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  23. Oberdieck, R., Diangelakis, N., Nascu, I., Papathanasiou, M., Sun, M., Avraamidou, S., Pistikopoulos, E.: On multi-parametric programming and its applications in process systems engineering. Chem. Eng. Res. Des. 116, 61–82 (2016b)

    Article  Google Scholar 

  24. Oberdieck, R., Diangelakis, N., Papathanasiou, M., Nascu, I., Pistikopoulos, E.: Pop—parametric optimization toolbox. Ind. Eng. Chem. Res. 55(33), 8979–8991 (2016c)

    Article  Google Scholar 

  25. Olaru, S., Dumur, D.: On the continuity and complexity of control laws based on multiparametric linear programs, pp. 5465–5470 (2006)

  26. Pramanik, S., Roy, T.: Fuzzy goal programming approach to multilevel programming problems. Eur. J. Oper. Res. 176(2), 1151–1166 (2007)

    Article  MATH  Google Scholar 

  27. Saharidis, G.K., Ierapetritou, M.G.: Resolution method for mixed integer bi-level linear problems based on decomposition technique. J. Global Optim. 44(1), 29–51 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  28. Sakawa, M., Matsui, T.: Interactive fuzzy stochastic multi-level 0–1 programming using tabu search and probability maximization. Expert Syst. Appl. 41(6), 2957–2963 (2014)

    Article  Google Scholar 

  29. Sakawa, M., Nishizaki, I., Uemura, Y.: Interactive fuzzy programming for multilevel linear programming problems. Comput. Math. Appl. 36(2), 71–86 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  30. Sakawa, M., Nishizaki, I., Hitaka, M.: Interactive fuzzy programming for multi-level 0–1 programming problems through genetic algorithms. Eur. J. Oper. Res. 114(3), 580–588 (1999)

    Article  MATH  Google Scholar 

  31. Shih, H.S., Lai, Y.J., Lee, E.: Fuzzy approach for multi-level programming problems. Comput. Oper. Res. 23(1), 73–91 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  32. Sinha, S.: A comment on Anandalingam (1988). A mathematical programming model of decentralized multi-level systems. J. Oper. Res. Soc. 39: 1021–1033. J. Oper. Res. Soc. 52(5), 594–596 (2001)

    Article  Google Scholar 

  33. Sinha, S.: Fuzzy mathematical programming applied to multi-level programming problems. Comput. Oper. Res. 30(9), 1259–1268 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  34. Spjtvold, J., Tndel, P., Johansen, T.: A method for obtaining continuous solutions to multiparametric linear programs. IFAC Proc. Vol. 16, 253–258 (2005)

    Article  Google Scholar 

  35. Street, A., Moreira, A., Arroyo, J.: Energy and reserve scheduling under a joint generation and transmission security criterion: an adjustable robust optimization approach. IEEE Trans. Power Syst. 29(1), 3–14 (2014)

    Article  Google Scholar 

  36. Wen, U.P., Bialas, W.: The hybrid algorithm for solving the three-level linear programming problem. Comput. Oper. Res. 13(4), 367–377 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  37. White, D.: Penalty function approach to linear trilevel programming. J. Optim. Theory Appl. 93(1), 183–197 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  38. Xu, P., Wang, L.Z.: An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41, 309–318 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  39. Xu, X., Meng, Z., Shen, R.: A tri-level programming model based on conditional value-at-risk for three-stage supply chain management. Comput. Ind. Eng. 66(2), 470–475 (2013)

    Article  Google Scholar 

  40. Yao, Y., Edmunds, T., Papageorgiou, D., Alvarez, R.: Trilevel optimization in power network defense. IEEE Trans. Syst. Man Cybern. Part C Appl. Rev. 37(4), 712–718 (2007)

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to the Department of Chemical Engineering and the Faculty of Engineering of Imperial College London for an EPSRC-funded Doctoral Training Partnership (DTP) studentship. Financial support from Texas A&M University and Texas A&M Energy Institute is also gratefully acknowledged.

Author information

Authors and Affiliations

  1. Centre for Process Systems Engineering, Imperial College London, London, SW7 2AZ, UK

    Styliani Avraamidou

  2. Texas A & M Energy Institute, Artie McFerrin Department of Chemical Engineering, Texas A & M University, College Station, TX, United States

    Styliani Avraamidou & Efstratios N. Pistikopoulos

Authors
  1. Styliani Avraamidou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Efstratios N. Pistikopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Efstratios N. Pistikopoulos.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Avraamidou, S., Pistikopoulos, E.N. Multi-parametric global optimization approach for tri-level mixed-integer linear optimization problems. J Glob Optim 74, 443–465 (2019). https://doi.org/10.1007/s10898-018-0668-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-018-0668-4

Keywords

Search

Navigation