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

  • Constraint programming, Streamliners

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. 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. 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. Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063

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

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

  5. Closed frequent itemset mining with arbitrary side constraints

    Kocak, G., Akgun, O., Miguel, I. J. & Nightingale, P. W., 17 Nov 2018, 2018 IEEE International Conference on Data Mining Workshops (ICDMW). Tong, H., Li, Z. J., Zhu, F. & Yu, J. (eds.). IEEE Computer Society, p. 1224 - 1232 9 p. 8637581

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

ID: 261625048

Top