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

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.