DROPS

Document

DOI: 10.4230/LIPIcs.CP.2022.38

Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints

Authors: Felix Ulrich-Oltean, Peter Nightingale, and James Alfred Walker

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract

Many constraint satisfaction and optimisation problems can be solved effectively by encoding them as instances of the Boolean Satisfiability problem (SAT). However, even the simplest types of constraints have many encodings in the literature with widely varying performance, and the problem of selecting suitable encodings for a given problem instance is not trivial. We explore the problem of selecting encodings for pseudo-Boolean and linear constraints using a supervised machine learning approach. We show that it is possible to select encodings effectively using a standard set of features for constraint problems; however we obtain better performance with a new set of features specifically designed for the pseudo-Boolean and linear constraints. In fact, we achieve good results when selecting encodings for unseen problem classes. Our results compare favourably to AutoFolio when using the same feature set. We discuss the relative importance of instance features to the task of selecting the best encodings, and compare several variations of the machine learning method.

Cite as

Felix Ulrich-Oltean, Peter Nightingale, and James Alfred Walker. Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ulricholtean_et_al:LIPIcs.CP.2022.38,
  author =	{Ulrich-Oltean, Felix and Nightingale, Peter and Walker, James Alfred},
  title =	{{Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.38},
  URN =		{urn:nbn:de:0030-drops-166670},
  doi =		{10.4230/LIPIcs.CP.2022.38},
  annote =	{Keywords: Constraint programming, SAT encodings, machine learning, global constraints, pseudo-Boolean constraints, linear constraints}
}

Search Results

Documents authored by Ulrich-Oltean, Felix

Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message