A simplex-based branch-and-cut method for solving integer tri-level programming problems
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
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
- Tri-level programming
- integer programming
- branch-and-cut
- valid inequalities
MSC
References
-
[1]
N. Alguacil, A. Delgadillo, J. M. Arroyo, A tri-level programming approach for electric grid defense planning, Comput. Oper. Res., 41 (2014), 282--290
-
[2]
S. Avraamidou, E. N. Pistikopoulos, Multi-parametric global optimization approach for tri-level mixed-integer linear optimization problems, J. Global Optim., 74 (2019), 443--465
-
[3]
J. F. Bard, An investigation of the linear three level programming problem, IEEE Trans. Systems Man Cybernet., 14 (1984), 711--717
-
[4]
J. F. Bard, Optimality conditions for the bi-level programming problem, Naval Res. Log. Quar., 31 (1984), 13--26
-
[5]
G. Cornuéjols, Valid inequalities for mixed integer linear programs, Math. Program., 112 (2008), 3--44
-
[6]
S. Dempe, F. M. Kue, Solving discrete linear bilevel optimization problems using the optimal value reformulation, J. Glob. Optim., 68 (2017), 255--277
-
[7]
S. T. DeNegre, T. K. Ralphs, A Branch-and-cut Algorithm for Integer Bilevel Linear Programs, In: Operations Research and Cyber-Infrastructure. Operations Research/Computer Science Interfaces (Springer, Boston), 47 (2009), 65--78
-
[8]
N. P. Faisca, M. P. Saraiva, B. Rustem, N. E. Pistikopoulos, A multiparametric programming approach for multilevel hierarchical and decentralized optimization problems, Comput. Manag. Sci., 6 (2009), 377--397
-
[9]
M. Fischetti, I. Ljubić, M. Monaci, M. Sinnl, Intersection Cuts for Bilevel Optimization, In: Integer programming and combinatorial optimization (Springer, Switzerland), 2016 (2016), 77--88
-
[10]
M. Fischetti, I. Ljubic, M. Monaci, M. Sinnl, A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs, Oper. Res., 65 (2017), 1615--1637
-
[11]
C. Florensa, P. Garcia-Herreros, P. Misra, E. Arslan, S. Mehta, I. E. Grossmann, Capacity planning with competitive decision-makers: Trilevel MILP formulation, degeneracy, and solution approaches, European J. Oper. Res., 262 (2017), 449--463
-
[12]
T. R. Kannan, G. Dinakaran, N. J. Lavanya, A Graphical Approach for Solving Three Variable Linear Programming Problems, Recent Developments in Materials Processing (RDMP--04), Bharathiyar College of Engineering and Technology, Karaikal, India (2004)
-
[13]
A. M. Kassa, S. M. Kassa, A multi-parametric programming algorithm for special classes of non-convex multilevel optimization problems, Int. J. Optim. Control. Theor. Appl. IJOCTA, 3 (2013), 133--144
-
[14]
A. M. Kassa, S. M. Kassa, A branch-and-bound multi-parametric programming approach for non-convex multilevel optimization with polyhedral constraints, J. Glob. Optim., 64 (2016), 745--764
-
[15]
G. Y. Ke, J. H. Bookbinder, Coordinating the discount policies for retailer, wholesaler, and less-than-truckload carrier under price-sensitive demand: A tri-level optimization approach, Int. J. Pro. Econ., 196 (2018), 82--100
-
[16]
K. Lachhwani, A. Dwivedi, Bi-level and Multi-Level Programming Problems: Taxonomy of Literature Review and Research Issues, Arch. Comput. Methods Eng., 25 (2018), 847--877
-
[17]
J. V. Outrata, On the numerical solution of a class of Stackelberg problems, Z. Oper. Res., 34 (1990), 255--277
-
[18]
A. S. Safaei, S. Farsad, M. M. Paydar, Robust bi-level optimization of relief logistics operations, Appl. Math. Model., 56 (2018), 359--380
-
[19]
G. K. Saharidis, M. G. Ierapetritou, Resolution method for mixed integer bi-level linear problems based on decomposition technique, J. Global Optim., 44 (2009), 29--51
-
[20]
M. Sakawa, T. Matsui, Interactive fuzzy stochastic multi-level 0--1 programming using tabu search and probability maximization, Expert Syst. Appl., 41 (2014), 2957--2963
-
[21]
M. Sakawa, I. Nishizaki, M. Hitaka, Interactive fuzzy programming for multi-level 0--1 programming problems through genetic algorithms, Eur. J. Oper. Res., 114 (1999), 580--588
-
[22]
S. S. Sana, A production-inventory model of imperfect quality products in a three-layer supply chain, Decis. Support Syst., 50 (2011), 539--547
-
[23]
S. Tahernejad, T. K. Ralphs, S. T. DeNegre, A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation, Math. Program. Comput., 12 (2020), 529--568
-
[24]
U.-P. Wen, Mathematical methods for multilevel linear programming, Ph.D. Dissertation, Dept. Industrial Engineering, State University of New York, Buffalo, New York (1981)
-
[25]
U.-P. Wen, W. F. Bialas, The hybrid algorithm for solving the three-level linear programming problem, Comput. Oper. Res., 13 (1986), 367--377
-
[26]
D. J. White, Penalty function approach to linear trilevel programming, J. Optim. Theory Appl., 93 (1997), 183--197
-
[27]
A. T. Woldemariam, S. M. Kassa, Systematic evolutionary algorithm for general multilevel Stackelberg problems with bounded decision variables (SEAMSP), Ann. Oper. Res., 229 (2015), 771--790
-
[28]
X. Xu, Z. Meng, R. Shen, A tri-level programming model based on conditional value-at-risk for three-stage supply chain management, Comput. Ind. Eng., 66 (2013), 470--475
-
[29]
P. Xu, L. Wang, An exact algorithm for the bi-level mixed integer linear programming problem under three simplifying assumptions, Comput. Oper. Res., 41 (2014), 309--318
-
[30]
Y. Yao, T. Edmunds, D. Papageorgiou, R. Alvarez, Tri-level optimization in power network defense, IEEE Trans. Syst. Man Cybern., 37 (2007), 712--718
-
[31]
G. Zhang, J. Lu, J. Montero, Y. Zeng, Model, solution concept, and Kth-best algorithm for linear trilevel programming, Inf. Sci., 180 (2010), 481--492