Exploiting incomparability in solution dominance: improving general purpose constraint-based mining

Gokberk Kocak, Ozgur Akgun, Tias Guns, Ian James Miguel

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In data mining, finding interesting patterns is a challenging task. Constraint-based mining is a well-known approach to this, and one for which constraint programming has been shown to be a well-suited and generic framework. Constraint dominance programming (CDP) has been proposed as an extension that can capture an even wider class of constraint-based mining problems, by allowing us to compare relations between patterns. In this paper we improve CDP with the ability to specify an incomparability condition. This allows us to overcome two major shortcomings of CDP: finding dominated solutions that must then be filtered out after search, and unnecessarily adding dominance blocking constraints between incomparable solutions. We demonstrate the efficacy of our approach by extending the problem specification language ESSENCE and implementing it in a solver-independent manner on top of the constraint modelling tool CONJURE. Our experiments on pattern mining tasks with both a CP solver and a SAT solver show that using the incomparability condition during search significantly improves the efficiency of dominance programming and reduces (and often eliminates entirely) the need for post-processing to filter dominated solutions.
Original languageEnglish
Title of host publicationECAI 2020
Subtitle of host publication24th European Conference on Artificial Intelligence
EditorsGiuseppe De Giacomo, Alejandro Catala, Bistra Dilkina, Michela Milano, Senén Barro, Alberto Bugarín, Jérôme Lang
Place of PublicationAmsterdam
PublisherIOS Press
Number of pages8
ISBN (Electronic)9781643681016
ISBN (Print)9781643681009
Publication statusPublished - 29 Aug 2020
Event24th European Conference on Artificial Intelligence (ECAI2020) - Santiago de Compostela, Spain
Duration: 29 Aug 20202 Sept 2020
Conference number: 24

Publication series

NameFrontiers in artificial intelligence and applications
ISSN (Print)0922-6389
ISSN (Electronic)1879-8314


Conference24th European Conference on Artificial Intelligence (ECAI2020)
Abbreviated titleECAI2020
CitySantiago de Compostela
Internet address


Dive into the research topics of 'Exploiting incomparability in solution dominance: improving general purpose constraint-based mining'. Together they form a unique fingerprint.

Cite this