Tri-Level Mixed-Integer Linear Programming Problems: Solution Approaches and Applications

Abstract

Multi-level programming has been suggested as a suitable methodology for modelling the interactions between the different levels of decisions in organizations that follow a hierarchical structure. It has been applied in different fields such as revenue and energy management. Due to the rise of decentralized decision-making and the need for efficient algorithms, the overarching motivation of this thesis is to develop algorithms suitable for solving multi-level programming problems and testing them on practical applications. First, we conduct a bibliometric analysis of the literature to categorize the major topics of study and solution methodologies. In addition, we identify research gaps and future research directions. Second, we direct our focus to developing efficient algorithms for solving specific classes of linear tri-level programs. In Chapter 3, we propose three heuristic-based approaches; each heuristic type offers a trade-off between solution quality and computational time. To illustrate our solution approaches, we present an application for defending critical infrastructure to improve its resilience against intentional attacks. In Chapter 4 we study bi-level mixed-integer linear problems and a general class of tri-level programs by proposing a general-purpose algorithm capable of handling mixed-integer variables in both levels of a bi-level linear program and solving a general class of tri-level mixed-integer programs with a convex optimization problem being at the most lower-level. In chapter 5, we examine a three-level non-cooperative game with perfect information that can have a min-max-min or a max-min-max structure. We propose a heuristically-enhanced exact algorithm. We demonstrate the proposed algorithm on two applications: defending critical infrastructure and the capacitated lot-sizing problem with the capability of interdiction and fortification.