DROPS

Document

DOI: 10.4230/LIPIcs.CP.2022.18

A Framework for Generating Informative Benchmark Instances

Authors: Nguyen Dang, Özgür Akgün, Joan Espasa, Ian Miguel, and Peter Nightingale

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

Abstract

Benchmarking is an important tool for assessing the relative performance of alternative solving approaches. However, the utility of benchmarking is limited by the quantity and quality of the available problem instances. Modern constraint programming languages typically allow the specification of a class-level model that is parameterised over instance data. This separation presents an opportunity for automated approaches to generate instance data that define instances that are graded (solvable at a certain difficulty level for a solver) or can discriminate between two solving approaches. In this paper, we introduce a framework that combines these two properties to generate a large number of benchmark instances, purposely generated for effective and informative benchmarking. We use five problems that were used in the MiniZinc competition to demonstrate the usage of our framework. In addition to producing a ranking among solvers, our framework gives a broader understanding of the behaviour of each solver for the whole instance space; for example by finding subsets of instances where the solver performance significantly varies from its average performance.

Cite as

Nguyen Dang, Özgür Akgün, Joan Espasa, Ian Miguel, and Peter Nightingale. A Framework for Generating Informative Benchmark Instances. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dang_et_al:LIPIcs.CP.2022.18,
  author =	{Dang, Nguyen and Akg\"{u}n, \"{O}zg\"{u}r and Espasa, Joan and Miguel, Ian and Nightingale, Peter},
  title =	{{A Framework for Generating Informative Benchmark Instances}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{18:1--18:18},
  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.18},
  URN =		{urn:nbn:de:0030-drops-166479},
  doi =		{10.4230/LIPIcs.CP.2022.18},
  annote =	{Keywords: Instance generation, Benchmarking, Constraint Programming}
}

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 Nightingale, Peter

A Framework for Generating Informative Benchmark Instances

Abstract

Cite as

Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message