Skip to content

Research at St Andrews

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

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

Abstract

We extend automatic instance generation methods to allow cross-paradigm comparisons. We demonstrate that it is possible to completely automate the search for benchmark instances that help to discriminate between solvers. Our system starts from a high level human-provided problem specification, which is translated into a specification for valid instances. We use the automated algorithm configuration tool irace to search for instances, which are translated into inputs for both MIP and CP solvers by means of the Conjure, Savile Row, and MiniZinc tools. These instances are then solved by CPLEX and Chuffed, respectively. We constrain our search for instances by requiring them to exhibit a significant advantage for MIP over CP, or vice versa. Experimental results on four optimisation problem classes demonstrate the effectiveness of our method in identifying instances that highlight differences in performance of the two solvers.

Close

Details

Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication17th International Conference, CPAIOR 2020, Vienna, Austria, September 21–24, 2020, Proceedings
EditorsEmmanuel Hebrard, Nysret Musliu
Place of PublicationCham
PublisherSpringer
Pages41-51
Number of pages11
ISBN (Electronic)9783030589424
ISBN (Print)9783030589417
DOIs
Publication statusPublished - 2020
Event17th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2020 - Vienna, Online, Austria
Duration: 21 Sep 202024 Sep 2020
https://cpaior2020.dbai.tuwien.ac.at/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12296 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2020
CountryAustria
CityVienna, Online
Period21/09/2024/09/20
Internet address

    Research areas

  • Constraint Programming, Instance generation, MIP

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

View graph of relations

Related by author

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

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

  3. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P., 13 Jul 2018, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

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

  4. Automatic discovery and exploitation of promising subproblems for tabulation

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W. & Salamon, A. Z., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 11008).

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

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

    Kocak, G., Akgun, O., Guns, T. & Miguel, I. J., 29 Aug 2020, ECAI 2020: 24th European Conference on Artificial Intelligence. De Giacomo, G., Catala, A., Dilkina, B., Milano, M., Barro, S., Bugarín, A. & Lang, J. (eds.). Amsterdam: IOS Press, p. 331-338 8 p. (Frontiers in artificial intelligence and applications; vol. 325).

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

ID: 270822702

Top