Our seminars take place on Wednesdays between 12:00 - 2:00 PM in the Center for Innovation and Transfer of Natural Sciences and Engineering Knowledge (building A0, wing B1, room 228).

Sign up to our newsletter

For your convenience we would like to kindly invite you to sign up to our newsletter. After filling in the fields below and submitting the form, please check your e-mail account and confirm the registration.
Email *

Visit counter

Online: 1
Total: 34746

April 4, 2017, Prof. Luis Baptista, Polytechnic Institute of Portalegre, Portugal, “Using Restarts on Constraint Programming over Finite Domains”


Abstract: Constraint Satisfaction Problems (CSPs) are a well-known case of NP-complete problems. They have extensive application in areas such as scheduling, timetabling, resources allocation, combinatorial mathematics, games and puzzles, and many other fields of computer science and engineering. Constraint Programming over Finite Domains (CP(FD)) has been used, with great success, in efficiently solving hard CSPs. Satisfiability problems (SAT) are also a well-known case of NP-complete problems, whose algorithms share common techniques with CP(FD). One of the major progress of backtrack search algorithms for SAT was the combined use of restarts, nogood recording (learning) and heuristics based on restarts. We study the interplay of those techniques in the context of CP(FD). We focus on domain splitting branching scheme, using restarts and nogood recording from restarts. From the empirical study we found an improvement to the fail-first heuristic that uses information from nogoods. In some classes of problems we found that the joint use of restarts, nogoods and heuristics have shown improvements of the algorithms. In fact, when studying the interplay of restarts strategies, heuristics and nogoods from restarts in CP(FD) algorithms, we do not see improvements when using restarts per se, nor when adding nogoods; but, when adding a third component, heuristics using information from nogoods, promising results can be achieved.

NoticeThis seminar will exceptionally take place on April, 4 2017 at 3.00 p.m. in room 127.


Comments are closed.