Learning Variable Activity Initialisation for Lazy Clause Generation Solvers

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

4 Downloads (Pure)

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 languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research - 18th International Conference, CPAIOR 2021, Proceedings
Subtitle of host publication18th International Conference Proceedings
EditorsPeter J. Stuckey
Place of PublicationCham
PublisherSpringer
Pages62-71
Number of pages10
ISBN (Electronic)978-3-030-78230-6
ISBN (Print)978-3-030-78229-0
DOIs
Publication statusPublished - 2021
EventCPAIOR 2021: 18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research - Hybrid at Vienna, Austria
Duration: 5 Jul 20218 Jul 2021
Conference number: 18th

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume12735
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceCPAIOR 2021
Country/TerritoryAustria
CityHybrid at Vienna
Period5/07/218/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-care
Otherwise 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.

Cite this