Constraint programming-based column generation

This paper surveys recent applications and advances of the constraint programming-based column generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by con- straint programming (CP). This framework has been introduced to solve crew assign- ment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using CP are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the CP-based column generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad hoc networks.