Integral Column Generation for Set Partitioning Problems with Side Constraints

The integral column generation algorithm (ICG) was recently introduced to solve set partitioning problems involving a very large number of variables. This primal algorithm generates a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution. ICG combines the well-known column generation algorithm and a primal algorithm called the integral simplex using decomposition algorithm (ISUD). In this paper, we develop a generalized version of ICG, denoted I2CG, that can solve efficiently large-scale set partitioning problems with side constraints. This new algorithm can handle the side constraints in the reduced problem of ISUD, in its complementary problem, or in both components. Computational experiments on instances of the airline crew pairing problem (CPP) and the multidepot vehicle routing problem with time windows show that the latter strategy is the most efficient one and I2CG significantly outperforms basic variants of two popular column generation heuristics, namely, a restricted master heuristic and a diving heuristic. For the largest tested CPP instance with 1,761 constraints, I2CG can produce in less than one hour of computational time more than 500 integer solutions leading to an optimal or near-optimal solution.

Automated summary

This paper introduces a generalized version of the integral column generation algorithm (ICG) called I2CG, which efficiently solves large-scale set partitioning problems with side constraints. Computational experiments show that I2CG outperforms other heuristics in solving the airline crew pairing problem and the multidepot vehicle routing problem with time windows.