Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Constraint-Level Advice for Shaving
 
conference paper

Constraint-Level Advice for Shaving

Szymanek, Radoslaw
•
Lecoutre, Christophe
2008
Logic Programming, Proceedings
24th International Conference on Logic Programming (ICLP)

This work concentrates on improving the robustness of constraint solvers by increasing the propagation strength of constraint models in a declarative and automatic manner. Our objective is to efficiently identify and remove shavable values during search. A value is shavable if as soon as it is assigned to its associated variable an inconsistency can be detected, making it possible to refute it. We extend previous work on shaving by using different techniques to decide if a given value is an interesting candidate for the shaving process. More precisely, we exploit the semantics of (global) constraints to suggest values, and reuse both the successes and failures of shaving later in search to tune shaving further. We illustrate our approach with two important global constraints, namely alldifferent and sum, and present the results of an experimentation obtained for three problem classes. The experimental results are quite encouraging: we are able to significantly reduce the number of search nodes (even by more than two orders of magnitude), and improve the average execution time by one order of magnitude.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-540-89982-2_52
Web of Science ID

WOS:000262929700047

Author(s)
Szymanek, Radoslaw
•
Lecoutre, Christophe
Date Issued

2008

Publisher

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa

Published in
Logic Programming, Proceedings
Series title/Series vol.

Lecture Notes In Computer Science; 5366

Start page

636

End page

650

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIA  
Event nameEvent placeEvent date
24th International Conference on Logic Programming (ICLP)

Udine, ITALY

Dec 09-13, 2008

Available on Infoscience
November 30, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/60687
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés