Analysis and algorithms to solve the Bilevel Assignment Problem

Analysis and algorithms to solve the Bilevel Assignment Problem In this thesis, the Bilevel Assignment Problem (BAP) is analyzed, and different exact, metaheuristic and matheuristic approaches are developed and implemented to solve it. The Assignment Problem (AP) is well known in the literature and the typical problem consists of assigning n origins i to n destinations j, such that, given a costs matrix of size n x n in which each value corresponds to each cost cij (of assigning origin i to destination j) the total cost obtained as a linear sum is maximized/minimized. Each origin and each destination must be assigned once. The very first algorithm that solves this problem efficiently was proposed by H.W. Kuhn in 1955 and is known as Hungarian Method, which by exploiting structural properties of the problem is able to solve it in O(n^3) time. On the other hand, in bilevel problems, there are two collaborative or conflicting decision makers, named the Leader, who acts first and the Follower that reacts depending on the Leader’s choice. On its general form, each one has its own decision variables and objective functions; however, sometimes they can be shared. There has been an increasing interest in bilevel programming on the scientific community since the 2000s, due to its capability to model complex problems in which more than one party are involved, e.g., the government (Leader) controlling policy variables (such as tax rates) to maximize employment or minimize the use of a resource, and the industry (Follower) being regulated and trying to maximize net incomes. In this BAP, the Leader is given n origins and n destinations, from which he must select k origins and k destinations. The Follower proceeds to solve the minimization Assignment Problem of the corresponding selected nodes, that form a costs matrix of size k x k. The Follower´s problem is easy; however, the Leader wants to make a selection in such a way that the optimal solution of the former is maximized. There exist some papers that work on the BAP, but the problem faced in this thesis has some particularities: the edges (costs) are common to both decision makers, and the objective functions of the Leader and the Follower are not aligned, since the former wants to maximize the solution of the latter, who in turn seeks to minimize the solution for the Assignment Problem. The structure of the thesis consists of a first chapter in which general theory is presented about Optimization problems. In the second one, specific concepts of the Assignment Problem and of Bilevel Programming are explained. The next three present different approaches and algorithms developed to solve the BAP, namely Exact, Metaheuristic and Matheuristic approaches. Each of them presents an optimized version. The results of these lasts are presented and compared in Chapter 6, together with the final conclusions of the thesis. Some complementary aspects are then presented in the Appendix, and finally the references are listed.