GELATO

GELATO: Gecode + Easy Local = A Tool for Optimization

Introduction

GELATO is a general tool for encoding optimization problems. Problems can modeled currently using several paradigms such as: Prolog, Minizinc, and Gecode. Other paradigms can be added. Solution search is performed by a hybrid solver (called GELATO) that exploits the potentiality of the Constraint Programming environment GECODE and of the Local Search framework EasyLocal++ for Large Neighborhood Search.
The user can modify a set of parameters for guiding the hybrid search. We test the tool on some difficult benchmarks, showing how one can set suitable parameters for the problem.
We compare the executions with pure local search, pure CP search, and with a state-of-the-art solver using large neighboring search, showing the potentials of our tool.

GELATO is based on two state-of-the-art, existing systems: the Gecode CP environment and the LS framework EasyLocal++.
Both these systems are free and open, strong and complete, written in C++, and with a growing community of users.

Our tool works with the releases 3.1.0-3.7.0 of Gecode.

At the modeling stage, we allow to use different programming paradigms. In particular, we currently work with Prolog and Minizinc, exploiting the front-end translator of Prolog and Minizinc to GECODE presented in ICLP2008 and we allow, of course, direct GECODE-modeling. The modeling capabilities of our tool can benefit from the front-end recently developed for the Haskell language and from other front-ends to Gecode, usually listed in the Gecode web-site. Some information about our front-end translator can be found here.

Download and Install

We remark that before installing GELATO, you have to properly intall Gecode and EasyLocal++

You can download therelease of GELATO for Gecode 3.7 from this link (September 26th, 2011).
The GELATO framework is stored into C++ header files, so there is no need to configure and install them. Once the header files have been downloaded in the selected directory, for example ./mydir/GELATO, you must add the following options to the compiler: -I./mydir/GELATO.

Here we report some detailed installation information.

In this page we report the source codes developed and the test we have performed t compare the performances of our hybrid tool GELATO with the pure CP and LS approaches, and with the state-of-the solver Comet, based on Large Neighborhood Search like GELATO.

At the end of this page we added the precompiled working GELATO code for the three benchmarks explained below. More details can be found in:

  • Raffaele Cipriano, Luca Di Gaspero, and Agostino Dovier.
    A Hybrid Solver for Large Neighborhood Search: Mixing Gecode and EasyLocal++.
    In HM 2009 6th International Workshop on Hybrid Metaheuristics. LNCS 5818, pp. 141-155, 2009.
  • Raffaele Cipriano, Luca Di Gaspero, and Agostino Dovier.
    GELATO: a multi-paradigm tool for Large Neighborhood Search.
    In Hybrid Metaheuristics (Talbi El-Ghazali ed) Springer Verlag, 2012. Studies in Computational Intelligence, Volume 434, 2013. Draft.

Benchmarks

We tested GELATO on three well-known COPs: the Asymmetric Travel Salesman Problem (ATSP), Minimum Energy Broadcast (MEB), and the Course TimeTabling (CTT).

ATSP

Given a complete directed graph G=(V,E) and a function c that assigns a cost to each directed edge (i,j), find a roundtrip of minimal total cost visiting each node exactly once. The edge costs might be not symmetric, i.e., in general c(i,j) != c(j,i).

Gecode model for ATSP.

EasyLocal++ definitions for ATSP: move definition and neighborhood explorer.

SICStus model for ATSP.

MEB

This problem is drawn from CSPLIB (number 48) and it is an optimization problem for the design of Wireless Network. Given a set of n nodes V = {1,…, n} forming a complete graph K, a source node s of V and and a cost function p : V x V –> R, representing the transmission cost between two nodes, the problem consists in finding a (directed) spanning tree rooted at s that minimizes a cost function f that measures the energy needed by a node for broadcasting information, and defined as follows.
Assume a tree t is given, and let us denote by next(i) the set of nodes reachable from a node i in t. Then f(t) = sum(i=1..n) max{p(i,j): {j € next(i) }.

Gecode model for MEB.

EasyLocal++ definitions for MEB: move definition and neighborhood explorer.

SICStus model for MEB.

CTT

This problem has been introduced as Track 3 of the second International Timetabling Competition held in 2007 (INFORMS Journal on Computing, 2009.). It consists in the weekly scheduling of the lectures of a set of university courses on the basis of a set of predefined curricula published by the University. For a complete definition on the problem look at the website of the competition.

Gecode model for CTT.

EasyLocal++ definitions for CTT: move definition and neighborhood explorer.

SICStus model for CTT.

Comparison Tests

We selected six instances for each problem a solved them using:

  1. a pure constraint programming approach in GECODE;
  2. a pure local search approach in EasyLocal++;
  3. a LNS meta-heuristics encoded in GELATO. Moreover we use the same model, the same meta-heuristics, and the same parameters used for (3) in the Comet system to guarantee a fair comparison with that system.

All computations were run on an AMD Opteron 2.2 GHz Linux Machine. We used Gecode 3.1.0, EasyLocal 2.0, and Comet 2.0.1.

Intances used are here: Instances

ATSP

instancebr17 instanceftv33 instanceftv55 instanceftv70 instancekro124p instanceftv170

MEB

instance20.02 instance20.03 instance20.08 instance20.14 instance20.24 instance20.29

CTT

instcomp01 instcomp04 instcomp07 instcomp09 instcomp11 instcomp14

Try it yourself!

You can download and install the executable solvers of the three problems, compiled for CygWin: ATSP MEB CTT

You only need to unzip the file, to read the README.txt file and to run the solver on a CygWin shell.

Comments are closed.