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 I\(^2\)CG, 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 involving up to 1761 constraints show that the latter strategy is the most efficient one and that I\(^2\)CG significantly outperforms two popular column generation heuristics, namely, a restricted master heuristic and a diving heuristic. For the largest tested instance, I\(^2\)CG can produce in less than one hour of computational time more than 500 integer solutions leading to an optimal or near-optimal solution.