A simplex-based branch-and-cut method for solving integer tri-level programming problems

Volume 25, Issue 3, pp 232--250 http://dx.doi.org/10.22436/jmcs.025.03.03
Publication Date: July 02, 2021 Submission Date: March 25, 2021 Revision Date: April 16, 2021 Accteptance Date: May 20, 2021

Authors

Ashenafi Awraris - Department of Mathematics, Addis Ababa University, P.O. Box 1176, Addis Ababa, Ethiopia. Berhanu Guta Wordofa - Department of Mathematics, Addis Ababa University, P.O. Box 1176, Addis Ababa, Ethiopia. Semu Mitiku Kassa - Department of Mathematics and Statistical Sciences, Botswana International University of Science \(\&\) Technology (BIUST), Botswana.


Abstract

Optimization problems involving three decision makers at three hierarchical decision levels are referred to as tri-level decision making problems. In particular in the case where all objective functions and constraints are linear, and all involved variables are required to take integer values is known as integer tri-level programming problems (T-ILP). It has been known that the general T-ILP is an NP-hard problem. So far there are very few attempts in the literature that finds an exact global solution for integer programming hierarchical problems beyond two levels. This paper proposes a novel approach based on a branch-and-cut (B\(\&\)C) framework for solving T-ILP. The convergence of the algorithm is proved. Numerical examples are used to demonstrate the performance of the proposed algorithm. Finally, the results of this study show that the proposed algorithm is promising and more efficient to solve T-ILP. Moreover, it has been indicated in the remark that the proposed algorithm can be modified and used to solve discrete multilevel programming problems of any number of levels.


Share and Cite

  • Share on Facebook
  • Share on Twitter
  • Share on LinkedIn
ISRP Style

Ashenafi Awraris, Berhanu Guta Wordofa, Semu Mitiku Kassa, A simplex-based branch-and-cut method for solving integer tri-level programming problems, Journal of Mathematics and Computer Science, 25 (2022), no. 3, 232--250

AMA Style

Awraris Ashenafi, Wordofa Berhanu Guta, Kassa Semu Mitiku, A simplex-based branch-and-cut method for solving integer tri-level programming problems. J Math Comput SCI-JM. (2022); 25(3):232--250

Chicago/Turabian Style

Awraris, Ashenafi, Wordofa, Berhanu Guta, Kassa, Semu Mitiku. "A simplex-based branch-and-cut method for solving integer tri-level programming problems." Journal of Mathematics and Computer Science, 25, no. 3 (2022): 232--250


Keywords


MSC


References