On the hybridization of constraint programming and local search techniques. Models and software tools

By Raffaele Cipriano
Università di Udine
1 Aprile 2011


This thesis aims to study the integration of the Constraint Programming and Local Search paradigms with three main goals in mind. First we want to combine together two free state-
of-the-art solvers for LS and CP in order to obtain a single framework for easily developing
hybrid techniques thus, exploiting the effectiveness of the basic solvers. Then, we define a
meta-heuristic modeling language to model CSPs and COPs as well as to define the meta-
heuristic to solve the problem. This language acts as high-level interface to access our framework functionalities. And finally, we test our tool on several benchmark problems, in order to show its effectiveness compared to other solvers for combinatorial problems.
In particular,  we present a framework called GELATO that integrates CP and LS techniques, defining a general LNS meta-heuristic that can be modified, tuned and adapted
to any optimization problem, with a limited programming effort. Instead of building a new
solver from scratch, we based our framework on two existing systems: the
Gecode CP environment  and the LS framework EasyLocal++.