Search Results

Documents authored by Nijssen, Siegfried

Document
DOI: 10.4230/LIPIcs.CP.2024.10
Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference

Authors: Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Weighted model counting (WMC) plays a central role in probabilistic reasoning. Given that this problem is #P-hard, harder instances can generally only be addressed using approximate techniques based on sampling, which provide statistical convergence guarantees: the longer a sampling process runs, the more accurate the WMC is likely to be. In this work, we propose a deterministic search-based approach that can also be stopped at any time and provides hard lower- and upper-bound guarantees on the true WMC. This approach uses a value heuristic that guides exploration first towards models with a high weight and leverages Limited Discrepancy Search to make the bounds converge faster. The validity, scalability, and convergence of our approach are tested and compared with state-of-the-art baseline methods on the problem of computing marginal probabilities in Bayesian networks and reliability estimation in probabilistic graphs.
Cite as

Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dubray_et_al:LIPIcs.CP.2024.10,
  author =	{Dubray, Alexandre and Schaus, Pierre and Nijssen, Siegfried},
  title =	{{Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.10},
  URN =		{urn:nbn:de:0030-drops-206956},
  doi =		{10.4230/LIPIcs.CP.2024.10},
  annote =	{Keywords: Projected Weighted Model Counting, Limited Discrepancy Search, Approximate Method, Probabilistic Inference}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.15
Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses

Authors: Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Weighted model counting, that is, counting the weighted number of satisfying assignments of a propositional formula, is an important tool in probabilistic reasoning. Recently, the use of projected weighted model counting (PWMC) has been proposed as an approach to formulate and answer probabilistic queries. In this work, we propose a new simplified modeling language based on PWMC in which probabilistic inference tasks are modeled using a conjunction of Horn clauses and a particular weighting scheme for the variables. We show that the major problems of inference for Bayesian Networks, network reachability and probabilistic logic programming can be modeled in this language. Subsequently, we propose a new, relatively simple solver that is specifically optimized to solve the PWMC problem for such formulas. Our experiments show that our new solver is competitive with state-of-the-art solvers on the major problems studied.
Cite as

Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dubray_et_al:LIPIcs.CP.2023.15,
  author =	{Dubray, Alexandre and Schaus, Pierre and Nijssen, Siegfried},
  title =	{{Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.15},
  URN =		{urn:nbn:de:0030-drops-190520},
  doi =		{10.4230/LIPIcs.CP.2023.15},
  annote =	{Keywords: Model Counting, Bayesian Networks, Probabilistic Networks}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2023.45
Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams (Short Paper)

Authors: Nicolas Golenvaux, Xavier Gillard, Siegfried Nijssen, and Pierre Schaus

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Regionalization is a crucial spatial analysis technique used for partitioning a map divided into zones into k continuous areas, optimizing the similarity of zone attributes within each area. This technique has a variety of applications in fields like urban planning, environmental management, and geographic information systems. The REDCAP algorithm is a well-known approach for addressing the regionalization problem. It consists of two main steps: first, it generates a spatially contiguous tree (SCT) representing the neighborhood structure of the set of spatial objects using a contiguity-constrained hierarchical clustering method. Second, it greedily removes k-1 edges from the SCT to create k regions. While this approach has proven to be effective, it may not always produce the most optimal solutions. We propose an alternative method for the second step, an exact dynamic programming (DP) formulation for the k-1 edges removal problem. This DP is solved using a multi-valued decision diagram (MDD)-based branch and bound solver leading to a more optimal solution. We compared our proposed method with the REDCAP state-of-the-art technique on real data and synthetic ones, using different instances of the regionalization problem and different supervised and unsupervised metrics. Our results indicate that our approach provides higher quality partitions than those produced by REDCAP at acceptable computational costs. This suggests that our method could be a viable alternative for addressing the regionalization problem in various applications.
Cite as

Nicolas Golenvaux, Xavier Gillard, Siegfried Nijssen, and Pierre Schaus. Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 45:1-45:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golenvaux_et_al:LIPIcs.CP.2023.45,
  author =	{Golenvaux, Nicolas and Gillard, Xavier and Nijssen, Siegfried and Schaus, Pierre},
  title =	{{Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{45:1--45:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.45},
  URN =		{urn:nbn:de:0030-drops-190825},
  doi =		{10.4230/LIPIcs.CP.2023.45},
  annote =	{Keywords: Regionalization, Redcap, Skater, Multivalued Decision Diagrams}
}
Document
DOI: 10.4230/DagRep.4.10.1
Constraints, Optimization and Data (Dagstuhl Seminar 14411)

Authors: Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Michele Sebag

Published in: Dagstuhl Reports, Volume 4, Issue 10 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14411 "Constraints, Optimization and Data". Constraint programming and optimization have recently received considerable attention from the fields of machine learning and data mining; similarly, machine learning and data mining have received considerable attention from the fields of constraint programming and optimization. The goal of the seminar was to showcase recent progress in these different areas, with the objective of working towards a common basis of understanding, which should help to facilitate future synergies.
Cite as

Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Michele Sebag. Constraints, Optimization and Data (Dagstuhl Seminar 14411). In Dagstuhl Reports, Volume 4, Issue 10, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{deraedt_et_al:DagRep.4.10.1,
  author =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Sebag, Michele},
  title =	{{Constraints, Optimization and Data (Dagstuhl Seminar 14411)}},
  pages =	{1--31},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{10},
  editor =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Sebag, Michele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.10.1},
  URN =		{urn:nbn:de:0030-drops-48901},
  doi =		{10.4230/DagRep.4.10.1},
  annote =	{Keywords: Data mining, constraint programming, machine learning}
}
Document
DOI: 10.4230/DagRep.1.5.61
Constraint Programming meets Machine Learning and Data Mining (Dagstuhl Seminar 11201)

Authors: Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Pascal Van Hentenryck

Published in: Dagstuhl Reports, Volume 1, Issue 5 (2011)

Abstract
This report documents the programme and the outcomes of Dagstuhl Seminar 11201 "Constraint Programming meets Machine Learning and Data Mining". Our starting point in this seminar was that machine learning and data mining have developed largely independently from constraint programming till now, but that it is increasingly becoming clear that there are many opportunities for interactions between these areas: on the one hand, data mining and machine learning can be used to improve constraint solving; on the other hand, constraint solving can be used in data mining in machine learning. This seminar brought together prominent researchers from both communities to discuss these opportunities.
Cite as

Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Pascal Van Hentenryck. Constraint Programming meets Machine Learning and Data Mining (Dagstuhl Seminar 11201). In Dagstuhl Reports, Volume 1, Issue 5, pp. 61-83, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{deraedt_et_al:DagRep.1.5.61,
  author =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Van Hentenryck, Pascal},
  title =	{{Constraint Programming meets Machine Learning and Data Mining (Dagstuhl Seminar 11201)}},
  pages =	{61--83},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{5},
  editor =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Van Hentenryck, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.5.61},
  URN =		{urn:nbn:de:0030-drops-32077},
  doi =		{10.4230/DagRep.1.5.61},
  annote =	{Keywords: Machine learning, data mining, constraint programming, constraints}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact