Skip to content

Research at St Andrews

Instance generation via generator instances

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

Abstract

Access to good benchmark instances is always desirable when developing new algorithms, new constraint models, or when comparing existing ones. Hand-written instances are of limited utility and are time-consuming to produce. A common method for generating instances is constructing special purpose programs for each class of problems. This can be better than manually producing instances, but developing such instance generators also has drawbacks. In this paper, we present a method for generating graded instances completely automatically starting from a class-level problem specification. A graded instance in our present setting is one which is neither too easy nor too difficult for a given solver. We start from an abstract problem specification written in the Essence language and provide a system to transform the problem specification, via automated type-specific rewriting rules, into a new abstract specification which we call a generator specification. The generator specification is itself parameterised by a number of integer parameters; these are used to characterise a certain region of the parameter space. The solutions of each such generator instance form valid problem instances. We use the parameter tuner irace to explore the space of possible generator parameters, aiming to find parameter values that yield graded instances. We perform an empirical evaluation of our system for five problem classes from CSPlib, demonstrating promising results.
Close

Details

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019, Proceedings
EditorsThomas Schiex, Simon de Givry
Place of PublicationCham
PublisherSpringer
Pages3-19
ISBN (Electronic)9783030300487
ISBN (Print)9783030300470
DOIs
Publication statusPublished - 2019
Event25th International Conference on Principles and Practice of Constraint Programming (CP 2019) - Stamford, United States
Duration: 30 Sep 20194 Oct 2019
Conference number: 25
http://cp2019.a4cp.org

Publication series

NameLecture Notes in Computer Science (Programming and Software Engineering)
Volume11802
ISSN (Print)0302-9743

Conference

Conference25th International Conference on Principles and Practice of Constraint Programming (CP 2019)
Abbreviated titleCP 2019
CountryUnited States
CityStamford
Period30/09/194/10/19
Internet address

    Research areas

  • Automated modelling, Instance generation, Parameter tuning

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. 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: 261625085

Top