Automatic core-guided reformulation via constraint explanation and condition learning

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

Abstract

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)
Pages8065-8072
Number of pages8
ISBN (Electronic)9781577358879
DOIs
Publication statusPublished - 2024
EventAAAI Conference on Artificial Intelligence 2024 - Vancouver, Canada
Duration: 20 Feb 202427 Feb 2024
Conference number: 38th
https://ojs.aaai.org/index.php/AAAI/issue/view/588 (AAAI-24 Technical Tracks 13)
https://ojs.aaai.org/index.php/AAAI/issue/view/589 (AAAI-24 Technical Tracks 14)
https://ojs.aaai.org/index.php/AAAI/issue/view/593 (AAAI-24 Technical Tracks 18)
https://aaai.org/aaai-conference/ (Website)

Publication series

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

Conference

ConferenceAAAI Conference on Artificial Intelligence 2024
Abbreviated titleAAAI 2024
Country/TerritoryCanada
CityVancouver
Period20/02/2427/02/24
Internet address

Keywords

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

Cite this