Abstract
Contemporary research explores the possibilities of integrating machine learning (ML) approaches with traditional combinatorial optimisation solvers. Since optimisation hybrid solvers, which combine propositional satisfiability (SAT) and constraint programming (CP), dominate recent benchmarks, it is surprising that the literature has paid limited attention to machine learning approaches for hybrid CP–SAT solvers. We identify the technique of minimal unsatisfiable subsets as promising to improve the performance of the hybrid CP–SAT lazy clause generation solver Chuffed. We leverage a graph convolutional network (GCN) model, trained on an adapted version of the MiniZinc benchmark suite. The GCN predicts which variables belong to an unsatisfiable subset on CP instances; these predictions are used to initialise the activity score of Chuffed’s Variable-State Independent Decaying Sum (VSIDS) heuristic. We benchmark the ML-aided Chuffed on the MiniZinc benchmark suite and find a robust 2.5% gain over baseline Chuffed on MRCPSP instances. This paper thus presents the first, to our knowledge, successful application of machine learning to improve hybrid CP–SAT solvers, a step towards improved automatic solving of CP models.
Original language | English |
---|---|
Title of host publication | Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 18th International Conference, CPAIOR 2021, Proceedings |
Subtitle of host publication | 18th International Conference Proceedings |
Editors | Peter J. Stuckey |
Place of Publication | Cham |
Publisher | Springer |
Pages | 62-71 |
Number of pages | 10 |
ISBN (Electronic) | 978-3-030-78230-6 |
ISBN (Print) | 978-3-030-78229-0 |
DOIs | |
Publication status | Published - 2021 |
Event | CPAIOR 2021: 18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research - Hybrid at Vienna, Austria Duration: 5 Jul 2021 → 8 Jul 2021 Conference number: 18th |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Publisher | Springer |
Volume | 12735 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | CPAIOR 2021 |
---|---|
Country/Territory | Austria |
City | Hybrid at Vienna |
Period | 5/07/21 → 8/07/21 |
Bibliographical note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-careOtherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
Fingerprint
Dive into the research topics of 'Learning Variable Activity Initialisation for Lazy Clause Generation Solvers'. Together they form a unique fingerprint.Datasets
-
VSIDS learning code: "Learning Variable Activity Initialisation for Lazy Clause Generation Solvers"
Yorke-Smith, N. (Creator), van Driel, R. (Creator) & Demirović, E. (Creator), TU Delft - 4TU.ResearchData, 19 Apr 2021
DOI: 10.4121/14259635
Dataset/Software: Software