We propose the integration and extension of the local branching search strategy in Constraint Programming (CP). Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree search. It has been successfully used in MIP where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. The integration of local branching in CP is not simply a matter of implementation, but requires a number of significant extensions (concerning the computation of the bound, cost-based filtering of the branching constraints, diversification, variable neighbourhood width and search heuristics) and can greatly benefit from the CP environment. In this paper, we discuss how such extensions are possible and provide some experimental results to demonstrate the practical value of local branching in CP.

CP-based Local Branching

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

Abstract

We propose the integration and extension of the local branching search strategy in Constraint Programming (CP). Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree search. It has been successfully used in MIP where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. The integration of local branching in CP is not simply a matter of implementation, but requires a number of significant extensions (concerning the computation of the bound, cost-based filtering of the branching constraints, diversification, variable neighbourhood width and search heuristics) and can greatly benefit from the CP environment. In this paper, we discuss how such extensions are possible and provide some experimental results to demonstrate the practical value of local branching in CP.
Proc. of the 14th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
-
-
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/64039
 Attenzione

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

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