Compiling CP subproblems to MDDs and d-DNNFs

Diego de Uña, Graeme Gange, Peter Schachte, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Modeling discrete optimization problems is not straightforward. It is often the case that precompiling a subproblem that involves only a few tightly constrained variables as a table constraint can improve solving time. Nevertheless, enumerating all the solutions of a subproblem into a table can be costly in time and space. In this work we propose using Multivalued Decision Diagrams (MDDs) and formulas in Deterministic Decomposable Negation Normal Form (d-DNNFs) rather than tables to compute and store all solutions of a subproblem. This, in turn, can be used to enhance the solver thanks to stronger propagation via specific propagators for these structures. We show how to precompile part of a problem into both these structures, which can then be injected back in the model by substituting the constraints it encodes, or simply adding it as a redundant constraint. Furthermore, in the case of MDDs, they can also be used to create edge-valued MDDs for optimization problems with an appropriate form. From our experiments we conclude that all three techniques are valuable in their own right, and show when each one should be chosen over the others.

Original languageEnglish
Pages (from-to)56-93
Number of pages38
JournalConstraints
Volume24
Issue number1
DOIs
Publication statusPublished - Jan 2019
Externally publishedYes

Keywords

  • Compilation
  • Constraint programming
  • d-DNNF
  • MDD
  • Multivalued decision diagrams
  • Presolving

Cite this

de Uña, Diego ; Gange, Graeme ; Schachte, Peter ; Stuckey, Peter J. / Compiling CP subproblems to MDDs and d-DNNFs. In: Constraints. 2019 ; Vol. 24, No. 1. pp. 56-93.
@article{873b96ad35e64a2ba28f92266dd67b51,
title = "Compiling CP subproblems to MDDs and d-DNNFs",
abstract = "Modeling discrete optimization problems is not straightforward. It is often the case that precompiling a subproblem that involves only a few tightly constrained variables as a table constraint can improve solving time. Nevertheless, enumerating all the solutions of a subproblem into a table can be costly in time and space. In this work we propose using Multivalued Decision Diagrams (MDDs) and formulas in Deterministic Decomposable Negation Normal Form (d-DNNFs) rather than tables to compute and store all solutions of a subproblem. This, in turn, can be used to enhance the solver thanks to stronger propagation via specific propagators for these structures. We show how to precompile part of a problem into both these structures, which can then be injected back in the model by substituting the constraints it encodes, or simply adding it as a redundant constraint. Furthermore, in the case of MDDs, they can also be used to create edge-valued MDDs for optimization problems with an appropriate form. From our experiments we conclude that all three techniques are valuable in their own right, and show when each one should be chosen over the others.",
keywords = "Compilation, Constraint programming, d-DNNF, MDD, Multivalued decision diagrams, Presolving",
author = "{de U{\~n}a}, Diego and Graeme Gange and Peter Schachte and Stuckey, {Peter J.}",
year = "2019",
month = "1",
doi = "10.1007/s10601-018-9297-2",
language = "English",
volume = "24",
pages = "56--93",
journal = "Constraints",
issn = "1383-7133",
publisher = "Springer-Verlag London Ltd.",
number = "1",

}

Compiling CP subproblems to MDDs and d-DNNFs. / de Uña, Diego; Gange, Graeme; Schachte, Peter; Stuckey, Peter J.

In: Constraints, Vol. 24, No. 1, 01.2019, p. 56-93.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Compiling CP subproblems to MDDs and d-DNNFs

AU - de Uña, Diego

AU - Gange, Graeme

AU - Schachte, Peter

AU - Stuckey, Peter J.

PY - 2019/1

Y1 - 2019/1

N2 - Modeling discrete optimization problems is not straightforward. It is often the case that precompiling a subproblem that involves only a few tightly constrained variables as a table constraint can improve solving time. Nevertheless, enumerating all the solutions of a subproblem into a table can be costly in time and space. In this work we propose using Multivalued Decision Diagrams (MDDs) and formulas in Deterministic Decomposable Negation Normal Form (d-DNNFs) rather than tables to compute and store all solutions of a subproblem. This, in turn, can be used to enhance the solver thanks to stronger propagation via specific propagators for these structures. We show how to precompile part of a problem into both these structures, which can then be injected back in the model by substituting the constraints it encodes, or simply adding it as a redundant constraint. Furthermore, in the case of MDDs, they can also be used to create edge-valued MDDs for optimization problems with an appropriate form. From our experiments we conclude that all three techniques are valuable in their own right, and show when each one should be chosen over the others.

AB - Modeling discrete optimization problems is not straightforward. It is often the case that precompiling a subproblem that involves only a few tightly constrained variables as a table constraint can improve solving time. Nevertheless, enumerating all the solutions of a subproblem into a table can be costly in time and space. In this work we propose using Multivalued Decision Diagrams (MDDs) and formulas in Deterministic Decomposable Negation Normal Form (d-DNNFs) rather than tables to compute and store all solutions of a subproblem. This, in turn, can be used to enhance the solver thanks to stronger propagation via specific propagators for these structures. We show how to precompile part of a problem into both these structures, which can then be injected back in the model by substituting the constraints it encodes, or simply adding it as a redundant constraint. Furthermore, in the case of MDDs, they can also be used to create edge-valued MDDs for optimization problems with an appropriate form. From our experiments we conclude that all three techniques are valuable in their own right, and show when each one should be chosen over the others.

KW - Compilation

KW - Constraint programming

KW - d-DNNF

KW - MDD

KW - Multivalued decision diagrams

KW - Presolving

UR - http://www.scopus.com/inward/record.url?scp=85056329039&partnerID=8YFLogxK

U2 - 10.1007/s10601-018-9297-2

DO - 10.1007/s10601-018-9297-2

M3 - Article

VL - 24

SP - 56

EP - 93

JO - Constraints

JF - Constraints

SN - 1383-7133

IS - 1

ER -