Core-guided and core-boosted search for CP

Graeme Gange, Jeremias Berg, Emir Demirović, Peter J. Stuckey

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

1 Citation (Scopus)

Abstract

Core-guided search has proven to be the state-of-the-art in finding optimal solutions for maximum Boolean satisfiability and these techniques have recently been successfully imported in constraint programming. While effective on a wide range of problems, the methods are direct translations of their propositional logic counterparts. We propose two reformulation techniques that take advantage of the rich formalism offered by constraint programming rather than relying on propositional logic strategies, and generalise two existing techniques to improve core-extraction and the overall performance. Our experiments demonstrate the effectiveness of our approaches over the conventional (core-guided) CP methods, both in terms of proving optimality and quickly computing high-quality solutions.

Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication17th International Conference, CPAIOR 2020 Vienna, Austria, September 21–24, 2020 Proceedings
EditorsEmmanuel Hebrard, Nysret Musliu
Place of PublicationCham Switzerland
PublisherSpringer
Pages205-221
Number of pages17
ISBN (Electronic)9783030589424
ISBN (Print)9783030589417
DOIs
Publication statusPublished - 2020
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2020 - Vienna, Austria
Duration: 21 Sep 202024 Sep 2020
Conference number: 17th
https://link.springer.com/book/10.1007/978-3-030-58942-4 (Proceedings)
https://cpaior2020.dbai.tuwien.ac.at (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12296
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2020
Abbreviated titleCPAIOR 2020
CountryAustria
CityVienna
Period21/09/2024/09/20
Internet address

Cite this