Abstract
Constraint programming is a highly successful technology for tackling complex combinatorial optimization problems. Any form of combinatorial optimization involves some form of search, and CP is very well adapted to make use of programmed search and strong inference to solve some problems that are out of reach of competing technologies. But much of the search that happens during a CP execution is effectively repeated. This arises from the combinatorial nature of the problems we are tackling. Learning about past unsuccessful searches and remembering this in an effective way can exponentially reduce the size of the search space. In this talk I will explain lazy clause generation, which is a hybrid constraint solving technique that steals all the best learning ideas from Boolean satisfiability solvers, but retains all the advantages of constraint programming. Lazy clause generation provides the state of the art solutions to a wide range of problems, and consistently outperforms other solving approaches in the MiniZinc challenge.
Original language | English |
---|---|
Title of host publication | Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Proceedings |
Publisher | Springer |
Pages | 5-6 |
Number of pages | 2 |
ISBN (Print) | 9783642406263 |
DOIs | |
Publication status | Published - 22 Oct 2013 |
Externally published | Yes |
Event | International Conference on Principles and Practice of Constraint Programming 2013 - Uppsala, Sweden Duration: 16 Sept 2013 → 20 Sept 2013 Conference number: 19th http://cp2013.a4cp.org/ |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 8124 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on Principles and Practice of Constraint Programming 2013 |
---|---|
Abbreviated title | CP 2013 |
Country/Territory | Sweden |
City | Uppsala |
Period | 16/09/13 → 20/09/13 |
Internet address |