Solving set partitioning problems using lagrangian relaxation

This thesis focuses on the set partitioning problem. Given a collection of subsets of a certain root set and costs associated to these subsets, the set partitioning problem is the problem of finding a minimum cost partition of the root set. Many real-life problems, such as vehicle routing and crew scheduling problems, can be formulated as set partitioning problems. The LaRSS solver is developed for solving set partitioning problems fast without using external linear programming solvers. The methods used include Lagrangian relaxation, preprocessing techniques and branch and bound. This thesis describes many research results coming from the development of LaRSS. Moreover, the performance of LaRSS is discussed and compared with the well-known optimization package CPLEX. Finally, two cases in the field of vehicle routing are described to illustrate the use of LaRSS in real-life situations.