In this PhD thesis, we study a variety of problems in the context of network design and optimization. The first half focuses on the Location Routing problem, in which Facility Location and Vehicle Routing are solved in an integrated fashion. We present an extensive literature study, in which we explain some of the most successful methods used to tackle this problem, and proceed to propose and analyze our own bifactor approximation. In the second part of the thesis, we study and propose methods for a variety of network security games, in which a central planner needs to decide on the distribution of security checks across a given network’s edges. The planner’s goal is to prevent potential intruders from reaching their destinations, while trying to have a limited impact on the traffic of regular users. We assess the performance of all our methods via extensive computational studies. We are especially interested in scalability, which is why we create and tackle large instances that cannot be solved by commercial solvers within reasonable times. Our experiments provide promising results, which not only confirm our theoretical analyses, but also illustrate our methods’ practical relevance and potential.