Solving the set partitioning problem using Lagrangean relaxation and column generation

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing. In this paper we propose a new dual heuristic and an exact method for the set partitioning problem. The dual heuristic combines Lagrangean relaxation and column generation and uses subgradient optimization to find an effective dual solution of the linear relaxation of the set partitioning problem. This procedure is faster than traditional simplex based methods, moreover, we show that the lower bound achieved dominates the bound obtained by the classic Lagrangean relaxation of the set partitioning constraints. The exact method iteratively solves a sequence of reduced set partitioning problems using a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method is easy to implement and it is competitive with the best branch and cut algorithms.