Hybrid Approaches for Rostering: A Case Study in the Integration of Constraint Programming and Local Search

  • Raffaele Cipriano
  • Luca Di Gaspero
  • Agostino Dovier
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4030)


Different approaches in the hybridization of constraint programming and local search techniques have been recently proposed in the literature. In this paper we investigate two of them, namely the employment of local search to improve a solution found by constraint programming and the exploitation of a constraint model to perform the exploration of the local neighborhood. We apply the two approaches to a real-world personnel rostering problem arising at the department of neurology of the Udine University hospital and we report on computational studies on both real-world and randomly generated structured instances. The results highlight the benefits of the hybridization approach w.r.t. their component algorithms.


Local Search Tabu Search Constraint Programming Local Search Algorithm Tabu List 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Aarts, E., Lenstra, J.K.: Local Search in Combinatorial Optimization. John Wiley & Sons, Chichester (1997)zbMATHGoogle Scholar
  2. 2.
    Apt, K.R.: Principles of Constraint Programming. Cambridge University Press, Cambridge (2003)CrossRefzbMATHGoogle Scholar
  3. 3.
    Burke, E.K., De Causmaecker, P., Van den Berghe, G., Van Landeghem, H.: The state of the art of nurse rostering. Journal of Scheduling 7(6), 441–499 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Carlsson, M., Ottosson, G., Carlson, B.: An open-ended finite domain constraint solver. In: Hartel, P.H., Kuchen, H. (eds.) PLILP 1997. LNCS, vol. 1292, pp. 191–206. Springer, Heidelberg (1997)CrossRefGoogle Scholar
  5. 5.
    Di Gaspero, L., Schaerf, A.: EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software — Practice & Experience 33(8), 733–765 (2003)CrossRefGoogle Scholar
  6. 6.
    Focacci, F., Laburthe, F., Lodi, A.: Local search and constraint programming. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, chapter Local Search and Constraint Programming, pp. 369–403. Kluwer Academic Publishers, Dordrecht (2003)Google Scholar
  7. 7.
    Jussien, N., Lhomme, O.: Local search with constraint propagation and conflict-based heuristic. Artificial Intelligence 139(1), 21–45 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Monfroy, E., Saubion, F., Lambert, T.: On hybridization of local search and constraint propagation. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol. 3132, pp. 299–313. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  9. 9.
    Pesant, G., Gendreau, M.: A constraint programming framework for local search methods. Journal of Heuristics 5, 255–279 (1999)zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Raffaele Cipriano
    • 1
  • Luca Di Gaspero
    • 2
  • Agostino Dovier
    • 1
  1. 1.Dip. di Matematica e Informatica 
  2. 2.Dip. di Ingegneria Elettrica, Gestionale e MeccanicaUniversità di UdineUdineItaly

Personalised recommendations