Core-guided model reformulation

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

Abstract

Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings
EditorsHelmut Simonis
Place of PublicationCham Switzerland
PublisherSpringer
Pages445-461
Number of pages17
ISBN (Electronic)9783030584757
ISBN (Print)9783030584740
DOIs
Publication statusPublished - 2020
EventInternational Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium
Duration: 7 Sep 202011 Sep 2020
Conference number: 26th
https://link.springer.com/book/10.1007/978-3-030-58475-7 (Proceedings)
https://cp2020.a4cp.org (Website)

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2020
Abbreviated titleCP2020
CountryBelgium
CityLouvain-la-Neuve
Period7/09/2011/09/20
Internet address

Cite this

Leo, K., Gange, G., Garcia De La Banda, M., & Wallace, M. (2020). Core-guided model reformulation. In H. Simonis (Ed.), Principles and Practice of Constraint Programming : 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings (pp. 445-461). (Lecture Notes in Computer Science ; Vol. 12333 ). Springer. https://doi.org/10.1007/978-3-030-58475-7_26