Skip to content

Research at St Andrews

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

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

DOI

Open Access permissions

Open

Abstract

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.
Close

Details

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
Pages331-338
Number of pages8
ISBN (Electronic)9781643681016
ISBN (Print)9781643681009
DOIs
Publication statusPublished - 29 Aug 2020
Event24th European Conference on Artificial Intelligence (ECAI2020) - Santiago de Compostela, Spain
Duration: 29 Aug 20202 Sep 2020
Conference number: 24
https://ecai2020.eu/

Publication series

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

Conference

Conference24th European Conference on Artificial Intelligence (ECAI2020)
Abbreviated titleECAI2020
CountrySpain
CitySantiago de Compostela
Period29/08/202/09/20
Internet address

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Discriminating instance generation from abstract specifications: a case study with CP and MIP

    Akgün, Ö., Dang, N., Miguel, I., Salamon, A. Z., Spracklen, P. & Stone, C., 2020, Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 17th International Conference, CPAIOR 2020, Vienna, Austria, September 21–24, 2020, Proceedings. Hebrard, E. & Musliu, N. (eds.). Cham: Springer, p. 41-51 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12296 LNCS).

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

  2. Towards improving solution dominance with incomparability conditions: a case-study using Generator Itemset Mining

    Kocak, G., Akgün, Ö., Miguel, I. & Guns, T., 30 Sep 2019, The 18th workshop on Constraint Modelling and Reformulation (ModRef 2019), Proceedings. 14 p.

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

  3. Cloud benchmarking for maximising performance of scientific applications

    Varghese, B., Akgun, O., Miguel, I. J., Thai, L. T. & Barker, A. D., 1 Jan 2019, In: IEEE Transactions on Cloud Computing. 7, 1, p. 170-182 13 p., 7553491.

    Research output: Contribution to journalArticlepeer-review

  4. Automatic streamlining for constrained optimisation

    Spracklen, P., Dang, N., Akgun, O. & Miguel, I. J., 2019, Principles and Practice of Constraint Programming: 25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019, Proceedings. Schiex, T. & de Givry, S. (eds.). Cham: Springer, p. 366-383 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11802 LNCS).

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

  5. Instance generation via generator instances

    Akgun, O., Dang, N., Miguel, I. J., Salamon, A. Z. & Stone, C. L., 2019, Principles and Practice of Constraint Programming: 25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019, Proceedings. Schiex, T. & de Givry, S. (eds.). Cham: Springer, p. 3-19 (Lecture Notes in Computer Science (Programming and Software Engineering); vol. 11802).

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

ID: 267211471

Top