Enhancing CP-based column generation for integer programs

This is a summary of the author’s Ph.D. thesis supervised by Federico Malucelli and defended on 15 May 2008 at the Politecnico di Milano. The thesis is written in English and is available from the author upon request. This work presents new methods for enhancing the Column Generation approach based on Constraint Programming when it is used for solving combinatorial optimization problems. The methods proposed focus on the interactions between the linear programming solver and the constraint programming solver, and on how they impact on both a single iteration and the overall execution of the Column Generation procedure. The result of this work is the design and implementation of general-purpose optimization algorithms, whose efficiency is proven by solving two very different problems: the Minimum Graph Coloring Problem and a resource allocation problem arising in Wireless Ad Hoc Networks.