TY - GEN
T1 - Automated Symmetry Breaking and Model Selection in Conjure
AU - Akgun, Ozgur
AU - Frisch, Alan M
AU - Gent, Ian Philip
AU - Hussain, Bilal Syed
AU - Jefferson, Christopher Anthony
AU - Kotthoff, Lars
AU - Miguel, Ian James
AU - Nightingale, Peter William
PY - 2013
Y1 - 2013
N2 - Constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. The Conjure automated constraint modelling system addresses this problem by automatically refining constraint models from problem specifications written in the Essence language. Essence provides familiar mathematical concepts like sets, functions and relations nested to any depth. To date, Conjure has been able to produce a set of alternative model kernels (i.e. without advanced features such as symmetry breaking or implied constraints) for a given specification. The first contribution of this paper is a method by which Conjure can break symmetry in a model as it is introduced by the modelling process. This works at the problem class level, rather than just individual instances, and does not require an expensive detection step after the model has been formulated. This allows Conjure to produce a higher quality set of models. A further limitation of Conjure has been the lack of a mechanism to select among the models it produces. The second contribution of this paper is to present two such mechanisms, allowing effective models to be chosen automatically.
AB - Constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. The Conjure automated constraint modelling system addresses this problem by automatically refining constraint models from problem specifications written in the Essence language. Essence provides familiar mathematical concepts like sets, functions and relations nested to any depth. To date, Conjure has been able to produce a set of alternative model kernels (i.e. without advanced features such as symmetry breaking or implied constraints) for a given specification. The first contribution of this paper is a method by which Conjure can break symmetry in a model as it is introduced by the modelling process. This works at the problem class level, rather than just individual instances, and does not require an expensive detection step after the model has been formulated. This allows Conjure to produce a higher quality set of models. A further limitation of Conjure has been the lack of a mechanism to select among the models it produces. The second contribution of this paper is to present two such mechanisms, allowing effective models to be chosen automatically.
U2 - 10.1007/978-3-642-40627-0_11
DO - 10.1007/978-3-642-40627-0_11
M3 - Conference contribution
SP - 107
EP - 116
BT - CP 2013 - Principles and Practice of Constraint Programming, 19th International Conference
ER -