Automatic core-guided reformulation via constraint explanation and condition learning

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


SAT and propagation solvers often underperform for optimisation models whose objective sums many single-variable terms. MaxSAT solvers avoid this by detecting and exploiting cores: subsets of these terms that cannot jointly take their lower bounds. Previous work demonstrated that manual analysis of cores can help define model reformulations likely to speed up solving for many model instances. This paper presents a method to automate this process. For each selected core the method identifies the instance constraints that caused it; infers the model constraints and parameters that explain how these instance constraints were formed; and learns the conditions that made those model constraints generate cores, while others did not. It then uses this information to reformulate the objective. The empirical evaluation shows this method can produce useful reformulations. Importantly, the method can be useful in other situations that require explaining a set of constraints.

Original languageEnglish
Title of host publicationThirty-Eighth AAAI Conference on Artificial Intelligence
EditorsMichael Wooldridge, Jennifer Dy, Sriraam Natarajan
Place of PublicationWashington DC USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages8
ISBN (Electronic)9781577358879
Publication statusPublished - 2024
EventAAAI Conference on Artificial Intelligence 2024 - Vancouver, Canada
Duration: 20 Feb 202427 Feb 2024
Conference number: 38th (AAAI-24 Technical Tracks 13) (AAAI-24 Technical Tracks 14) (AAAI-24 Technical Tracks 18) (Website)

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
Publisher Association for the Advancement of Artificial Intelligence (AAAI)
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


ConferenceAAAI Conference on Artificial Intelligence 2024
Abbreviated titleAAAI 2024
Internet address


  • CSO
  • Solvers and Tools
  • Constraint Learning and Acquisition
  • Constraint Optimization
  • Constraint Programming
  • Constraint Satisfaction
  • Mixed Discrete/Continuous Optimization
  • Satisfiability

Cite this