On the Hybridization of Constraint Programming and Local Search Techniques: Models and Software Tools

Author: 

Raffaele Cipriano

School: 

Univ. of Udine, DIMI

Supervisors: 

AGOSTINO DOVIER
LUCA DI GASPERO

Abstract: 

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 stateof-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 metaheuristic 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 this thesis we present a general 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++. GELATO inherits all the characteristics of these tools, providing all their functionalities as well as several new hybrid possibilities. It is worth noting that with GELATO it is possible to define one single model to exploit it to perform the search with different strategies. These strategies range from pure Locals Search to pure Constraint Programming through several degrees of hybridization (i.e., LNS strategies), controlled by parameter values. Moreover, GELATO does not require any modification of Gecode and EasyLocal++, not affecting their single development line. In this way every improvement of the basic tools, such as new functionalities or performance improvements, is immediately inherited by GELATO. GELATO is able to read and solve models encoded in Gecode or FlatZinc (a low-level target language for CSPs and COPs). In order to facilitate the use of the GELATO solver for users not versed in C++, we allow access to the GELATO functionalities from other high-level declarative languages, such as MiniZinc and SICStus Prolog. MiniZinc is a modeling language close to OPL, while SICStus Prolog is the state-of-the-art constraint logic programming language. A model written in MiniZinc or SICStus Prolog is translated into a FlatZinc encoding, that can be read and executed by the GELATO tool. We tested exhaustively GELATO on the following three benchmarks: 1. the Asymmetric Travel Salesman Problem, the asymmetric version of the well known TSP NP-hard problem, taken from the TSPLib; 2. the Minimum Energy Broadcast problem, an NP-hard optimization problem for the design of ad hoc Wireless Networks, drawn from CSPLib(number 48); 3. the Course Time Tabling problem, consisting of the weekly scheduling of the lectures for several university courses subjected to several given restrictions. This problem has been introduced as Track 3 of the second International Timetabling Competition held in 2007. We compared the performance of the GELATO hybrid approach with the approaches of pure Constraint Programming and pure Local Search as well as with the state-of-the-art framework for hybrid methods, i.e., the Comet language.

Graduated: 

Friday, April 1, 2011

PDF of thesis: