We present a hybrid solver (called ) that exploits the potentiality of a Constraint Programming (CP) environment (Gecode) and of a Local Search (LS) framework (EasyLocal ++). allows to easily develop and use hybrid meta-heuristic combining CP and LS phases (in particular Large Neighborhood Search). We tested some hybrid algorithms on different instances of the Asymmetric Traveling Salesman Problem: even if only naive LS strategies have been used, our meta-heuristics improve the standard CP search, in terms of both goodness of the solution reached and execution time. will be integrated into a more general tool to solve Constraint Satisfaction/Optimization Problems. Moreover, it can be seen as a new library for approximate and efficient searching in Gecode.

A hybrid solver for large neighborhood search: Mixing Gecode and EasyLocal++

CIPRIANO, Raffaele;DI GASPERO, Luca;DOVIER, Agostino
2009

Abstract

We present a hybrid solver (called ) that exploits the potentiality of a Constraint Programming (CP) environment (Gecode) and of a Local Search (LS) framework (EasyLocal ++). allows to easily develop and use hybrid meta-heuristic combining CP and LS phases (in particular Large Neighborhood Search). We tested some hybrid algorithms on different instances of the Asymmetric Traveling Salesman Problem: even if only naive LS strategies have been used, our meta-heuristics improve the standard CP search, in terms of both goodness of the solution reached and execution time. will be integrated into a more general tool to solve Constraint Satisfaction/Optimization Problems. Moreover, it can be seen as a new library for approximate and efficient searching in Gecode.
9783642049170
File in questo prodotto:
File Dimensione Formato  
hm2009.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Non pubblico
Dimensione 461.3 kB
Formato Adobe PDF
461.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/881985
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 3
social impact