DROPS

Artifact

Software

Peak-Utility Using CP

Authors: Chaima Hamdi, Nadjib Lazaar, Nassim Belmecheri, Djawad Bekkoucha, Said Jabbour, and Lakhdar Saïs

Abstract

Cite as

Chaima Hamdi, Nadjib Lazaar, Nassim Belmecheri, Djawad Bekkoucha, Said Jabbour, Lakhdar Saïs. Peak-Utility Using CP (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26906,
   title = {{Peak-Utility Using CP}}, 
   author = {Hamdi, Chaima and Lazaar, Nadjib and Belmecheri, Nassim and Bekkoucha, Djawad and Jabbour, Said and Sa\"{i}s, Lakhdar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:0537fa0fd6f91dd5f7ed23d393bea3d15fa4d0fd;origin=https://gitlab.lisn.upsaclay.fr/dpm/peakutility;visit=swh:1:snp:2bf6143c24e9d95716a7f862397ac25c22afb6cb;anchor=swh:1:rev:9a5a4da55a1f9c6f61bd5df4ad5592675377d6a6}{\texttt{swh:1:dir:0537fa0fd6f91dd5f7ed23d393bea3d15fa4d0fd}} (visited on 2026-07-13)},
   url = {https://gitlab.lisn.upsaclay.fr/dpm/peakutility.git},
   doi = {10.4230/artifacts.26906},
}

Document

DOI: 10.4230/LIPIcs.CP.2026.27

Utility-Peak Itemset Mining with Constraint Programming

Authors: Chaima Hamdi, Nadjib Lazaar, Nassim Belmecheri, Djawad Bekkoucha, Said Jabbour, and Lakhdar Saïs

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

High-Utility Itemset Mining (HUIM) aims to discover itemsets whose utility exceeds a given threshold. While specialized algorithms achieve strong performance, they lack flexibility when additional domain constraints must be incorporated. Constraint Programming (CP) offers a declarative alternative, but requires strong propagation to remain competitive. In this paper, we propose a CP framework for utility-driven pattern mining based on a parameterized global constraint that unifies the enumeration of High-Utility Itemsets (HUIs) and a new condensed representation called Utility-Peak Itemsets (UPIs). A UPI is an itemset whose utility is greater or equal than that of all its immediate subsets and supersets, capturing locally utility-maximal patterns. We study the computational complexity of UPI mining and show that deciding whether a high-utility UPI exists, for a given utility threshold, is NP-complete. Our global constraint, PeakUtility, integrates utility computation and upper-bound pruning through propagation rules. Experiments demonstrate that our approach performs competitively with the state of the art HUIM algorithms while preserving the modelling flexibility of CP.

Cite as

Chaima Hamdi, Nadjib Lazaar, Nassim Belmecheri, Djawad Bekkoucha, Said Jabbour, and Lakhdar Saïs. Utility-Peak Itemset Mining with Constraint Programming. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hamdi_et_al:LIPIcs.CP.2026.27,
  author =	{Hamdi, Chaima and Lazaar, Nadjib and Belmecheri, Nassim and Bekkoucha, Djawad and Jabbour, Said and Sa\"{i}s, Lakhdar},
  title =	{{Utility-Peak Itemset Mining with Constraint Programming}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{27:1--27:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.27},
  URN =		{urn:nbn:de:0030-drops-266595},
  doi =		{10.4230/LIPIcs.CP.2026.27},
  annote =	{Keywords: Constraint Programming, Pattern Mining, HUI Mining, Global Constraints, Declarative Data Mining}
}

Document

DOI: 10.4230/LIPIcs.CP.2022.27

On the Enumeration of Frequent High Utility Itemsets: A Symbolic AI Approach

Authors: Amel Hidouri, Said Jabbour, and Badran Raddaoui

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

Abstract

Mining interesting patterns from data is a core part of the data mining world. High utility mining, an active research topic in data mining, aims to discover valuable itemsets with high profit (e.g., cost, risk). However, the measure of interest of an itemset must primarily reflect not only the importance of items in terms of profit, but also their occurrence in data in order to make more crucial decisions. Some proposals are then introduced to deal with the problem of computing high utility itemsets that meet a minimum support threshold. However, in these existing proposals, all transactions in which the itemset appears are taken into account, including those in which the itemset has a low profit. So, no additional information about the overall utility of the itemset is taken into account. This paper addresses this issue by introducing a SAT-based model to efficiently find the set of all frequent high utility itemsets with the use of a minimum utility threshold applied to each transaction in which the itemset appears. More specifically, we reduce the problem of mining frequent high utility itemsets to the one of enumerating the models of a formula in propositional logic, and then we use state-of-the-art SAT solvers to solve it. Afterwards, to make our approach more efficient, we provide a decomposition technique that is particularly suitable for deriving smaller and independent sub-problems easy to resolve. Finally, an extensive experimental evaluation on various popular datasets shows that our method is fast and scale well compared to the state-of-the art algorithms.

Cite as

Amel Hidouri, Said Jabbour, and Badran Raddaoui. On the Enumeration of Frequent High Utility Itemsets: A Symbolic AI Approach. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hidouri_et_al:LIPIcs.CP.2022.27,
  author =	{Hidouri, Amel and Jabbour, Said and Raddaoui, Badran},
  title =	{{On the Enumeration of Frequent High Utility Itemsets: A Symbolic AI Approach}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{27:1--27: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.27},
  URN =		{urn:nbn:de:0030-drops-166564},
  doi =		{10.4230/LIPIcs.CP.2022.27},
  annote =	{Keywords: Data Mining, High Utility Itemsets, Propositional Satisfiability}
}

Search Results

Documents authored by Jabbour, Said

Peak-Utility Using CP

Abstract

Cite as

Utility-Peak Itemset Mining with Constraint Programming

Abstract

Cite as

On the Enumeration of Frequent High Utility Itemsets: A Symbolic AI Approach

Abstract

Cite as

Thanks for your feedback!

Could not send message