Discriminating instance generation for automated constraint model selection

Ian Gent, Bilal Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Glenna Nightingale, Peter Nightingale

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

One approach to automated constraint modelling is to generate, and then select from, a set of candidate models. This method is used by the automated modelling system Conjure. To select a preferred model or set of models for a problem class from the candidates Conjure produces, we use a set of training instances drawn from the target class. It is important that the training instances are discriminating. If all models solve a given instance in a trivial amount of time, or if no models solve it in the time available, then the instance is not useful for model selection. This paper addresses the task of generating small sets of discriminating training instances automatically. The instance space is determined by the parameters of the associated problem class. We develop a number of methods of finding parameter configurations that give discriminating training instances, some of them leveraging existing parameter-tuning techniques. Our experimental results confirm the success of our approach in reducing a large set of input models to a small set that we can expect to perform well for the given problem class.
Original languageEnglish
Title of host publicationin Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming
Pages356-365
DOIs
Publication statusPublished - 19 Aug 2014

Fingerprint

Dive into the research topics of 'Discriminating instance generation for automated constraint model selection'. Together they form a unique fingerprint.

Cite this