Local branching is a general purpose heuristic method which searches lo- cally around the best known solution by employing tree search. It has been success- fully used in Mixed-Integer Programming where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. We pro- pose the integration of local branching in Constraint Programming (CP). This inte- gration is not simply a matter of implementation, but requires a number of significant extensions. The original contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a cost-based filtering al- gorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with Time Windows.

Bounding, filtering and diversification in CP-based local branching

KIZILTAN, ZEYNEP;LODI, ANDREA;MILANO, MICHELA;PARISINI, FABIO
2012

Abstract

Local branching is a general purpose heuristic method which searches lo- cally around the best known solution by employing tree search. It has been success- fully used in Mixed-Integer Programming where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. We pro- pose the integration of local branching in Constraint Programming (CP). This inte- gration is not simply a matter of implementation, but requires a number of significant extensions. The original contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a cost-based filtering al- gorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with Time Windows.
Z. Kiziltan; A. Lodi; M. Milano; F. Parisini
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/116084
 Attenzione

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

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