Abstract
This thesis addresses a class of bi-level network design problems. We are interested in investigating applications from different domains and in developing exact algorithms to solve the corresponding bi-level network problem. In particular, we study a bi-level network design problem where the leader selects a part of the network to be activated, then, in the second level, the solution must be optimal for a network flow problem in the selected sub-network. In this thesis, three applications of this problem are studied: hazmats transportation, telecommunication, and social networks analysis. The second level problem in the first and the last applications is a shortest path problem while a minimum cost flow is required in the second application.The first studied problem is the fixed charge network design problem with shortest path constraints, which is modeled as a bi-level program and can be applied in hazardous transportation. For this problem, we propose two new binary integer programming (BILP) formulations inspired by path and cycle inequalities. We incorporate these formulations in a branch-and-cut algorithm and another cutting-plane based method. Numerical experiments are performed on real instances, and random data sets generated with different criteria to examine the difficulty of the instances. The results show that the proposed cutting plane algorithms can solve up to 19% more instances than the compact formulations.The second studied problem is the energy-aware traffic engineering while using multi-path routing to minimize link capacity utilization in ISP backbone networks. We propose a bi-level optimization model where the upper level represents the energy management function, and the lower one refers to the deployed multi-path routing protocol. Then, we reformulate it as a one-level MILP replacing the second level problem by different sets of flow optimality conditions. We further use these formulations to solve the problem with classical cutting plane and branch-and-cut algorithms. The computational experiments are performed on real instances to compare the proposed algorithms and to evaluate the efficiency of our model against existing single-path and multi-objective models.Finally, we study the problem of maximization influence in signed social networks. To the best of our knowledge, it is the first time that this problem is modeled as a bi-level programming problem. We reformulate the problem as one-level MILP models using three different optimality conditions of the shortest path problem appearing in the second level. These formulations are strengthened by adding a set of valid inequalities. Computational experiments are performed using random instances to compare the different proposed formulations. Finally, explicit solutions and bounds are proposed for particular cases of instances.