Those who cannot remember the past are condemned to repeat it

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

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 languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 19th International Conference, CP 2013, Proceedings
PublisherSpringer
Pages5-6
Number of pages2
ISBN (Print)9783642406263
DOIs
Publication statusPublished - 22 Oct 2013
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2013 - Uppsala, Sweden
Duration: 16 Sept 201320 Sept 2013
Conference number: 19th
http://cp2013.a4cp.org/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8124 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2013
Abbreviated titleCP 2013
Country/TerritorySweden
CityUppsala
Period16/09/1320/09/13
Internet address

Cite this