Constraint Programming Researchat York.pptVIP

Constraint Programming Researchat York What is Constraint Programming? Solve a combinatorial (optimisation) problem by Mapping it to the finite-domain constraint satisfaction problem (modelling) Characterise problem by a set of constraints that a solution must satisfy For optimisation, include an objective function Solving the constraint satisfaction problem Useful for solving a wide range of important, complex problems including scheduling, allocation, layout and configuration problems. Research on Modelling Modelling Bottleneck Modelling a problem as a constraint program requires moderate/great expertise. Hence constraint technology is used almost exclusively by large enterprises on problems with large payoff. Reducing the Modelling Bottleneck Systematise the knowledge of the expert. 2 to 3 years: We have been building models more and more systematically Embed this knowledge in a “compiler” that can reformulate a high-level problem specification into a set of constraints that can be executed efficiently using existing toolkits. CONJURE CONJUREAutomated Model Generation Given an abstract formal problem specification, in ESSENCE Generates a set of correct models Should include good models generated by experts These models are in ESSENCE, a subset of ESSENCE that is similar to what is provided by existing constraint toolkits ESSENCE Distinguishing Features of ESSENCE Generating Good Models Involves Expected Benefits of this Research Rigorous account of model generation Make study of modelling more systematic Reveal gaps in understanding Guide study of model selection by identifying decision points and available alternatives Useful for teaching, presenting, cataloguing Formal account of model generation Generator: CONJURE Proof checker Major step towards automated entire modelling process Research on Symmetry Breaking Symmetry in Constraint Models Symmetry in a model results in symmetry in the search space of partial assignments to variables. Example: Find 3 nat