Automated streamliner portfolios for constraint satisfaction problems

Justin Lewis Patrick John Spracklen, Nguyen Dang, Ozgur Akgun*, Ian James Miguel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Downloads (Pure)

Abstract

Constraint Programming (CP) is a powerful technique for solving large-scale combinatorial problems. Solving a problem proceeds in two distinct phases: modelling and solving. Effective modelling has a huge impact on the performance of the solving process. Even with the advance of modern automated modelling tools, search spaces involved can be so vast that problems can still be difficult to solve. To further constrain the model, a more aggressive step that can be taken is the addition of streamliner constraints, which are not guaranteed to be sound but are designed to focus effort on a highly restricted but promising portion of the search space. Previously, producing effective streamlined models was a manual, difficult and time-consuming task. This paper presents a completely automated process to the generation, search and selection of streamliner portfolios to produce a substantial reduction in search effort across a diverse range of problems. The results demonstrate a marked improvement in performance for both Chuffed, a CP solver with clause learning, and lingeling, a modern SAT solver.
Original languageEnglish
Article number103915
Number of pages24
JournalArtificial Intelligence
Volume319
Early online date5 Apr 2023
DOIs
Publication statusPublished - 1 Jun 2023

Keywords

  • Constraint programming
  • Constraint modelling
  • Constraint satisfaction problem
  • Algorithm selection

Fingerprint

Dive into the research topics of 'Automated streamliner portfolios for constraint satisfaction problems'. Together they form a unique fingerprint.

Cite this