Skip to content

Research at St Andrews

Automatic streamlining for constrained optimisation

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

Abstract

Augmenting a base constraint model with additional constraints can strengthen the inferences made by a solver and therefore reduce search effort. We focus on the automatic addition of streamliner constraints, which trade completeness for potentially very significant reduction in search. Recently an automated approach has been proposed, which produces streamliners via a set of streamliner generation rules. This existing automated approach to streamliner generation has two key limitations. First, it outputs a single streamlined model. Second, the approach is limited to satisfaction problems. We remove both limitations by providing a method to produce automatically a portfolio of streamliners, each representing a different balance between three criteria: how aggressively the search space is reduced, the proportion of training instances for which the streamliner admitted at least one solution, and the average reduction in quality of the objective value versus the unstreamlined model. In support of our new method, we present an automated approach to training and test instance generation, and provide several approaches to the selection and application of the streamliners from the portfolio. Empirical results demonstrate drastic improvements both to the time required to find good solutions early and to prove optimality on three problem classes.
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
Pages366-383
Number of pages18
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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11802 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

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

  • Constraint programming, Streamliners

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

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

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

  5. Athanor: high-level local search over abstract constraint specifications in Essence

    Attieh, S., Dang, N., Jefferson, C., Miguel, I. & Nightingale, P., 10 Aug 2019, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19). Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063 8 p.

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

ID: 261625048

Top