Invited Session Wed.1.H 3003A

Wednesday, 10:30 - 12:00 h, Room: H 3003A

Cluster 5: Constraint programming [...]

Modeling and reformulation


Chair: Mark G. Wallace



Wednesday, 10:30 - 10:55 h, Room: H 3003A, Talk 1

Mark G. Wallace
Inferring properties of models from properties of small instances

Coauthors: Maria J. Garcia de la Banda, Chris D. Mears


To solve large problem instances efficiently, expert modelers exploit properties of the problem
(model) that enable specialised solving methods to be applied. Examples include symmetry-breaking,
subproblem solution caching, introducing global constraints and other problem relaxations.
The automation of this process is a research challenge with a potentially huge practical impact.
Unfortunately automated analysis of large problem instances is computationally very costly, so
typically only "obvious'' properties can be detected and exploited.
This paper presents an approach which uses automated analysis of small instances to infer properties
of the problem model which can then be applied to solving large instances. To date the approach has
been successfully applied to symmetries and caching, and its application to problem relaxations is
the subject of our current research.



Wednesday, 11:00 - 11:25 h, Room: H 3003A, Talk 2

Helmut Simonis
Building global constraint models from positive examples

Coauthor: Nicolas Beldiceanu


We present a system which generates global constraint models from few positive examples of problem solutions. In contrast to previous constraint acquisition work, we present a novel approach based on the global constraint catalog and the Constraint Seeker tool which generates models for problems which can be expressed as regular conjunctions of similar constraints.
Our system first generates regular groupings of variables in the given samples. The Constraint Seeker is then used to find ranked, typical constraints which match all given positive examples. A dominance check, which removes implied constraints based on meta-data in the constraint catalog, leads to a final ranked set of candidate constraints for each problem.
The system is implemented in SICStus Prolog, and heavily relies on the constraint description and
evaluators in the global constraint catalog. We show results for more than 200 example problems,
ranging from puzzles to sports scheduling, placement and layout problems. The problems range from 4
to over 6000 variables, and use between one and 7000 samples, utilizing over 50 global constraints
of the catalog. We achieve an overall hit-rate of about 50%.



Wednesday, 11:30 - 11:55 h, Room: H 3003A, Talk 3

Ian Miguel
Towards automated constraint modelling with essence and conjure

Coauthors: Ozgur Akgun, Alan M. Frisch, Brahim Hnich, Christopher Jefferson


Constraint solving offers an efficient means of solving a variety of combinatorial problems. A critical and well-recognised bottleneck in applying constraints is the formulation of an effective constraint model of a given problem. Without help, it is very difficult for a novice user to formulate an effective (or even correct) model. This can lead to very long solution times, or to incorrect solutions. Our approach to this problem, described in this talk, is to allow the user to describe a problem in the specification language Essence without committing to a constraint model. Using a set of refinement rules, this specification is then transformed automatically into a constraint model using our Conjure system. Our empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of benchmark problems found in the literature. Next steps include choosing among the models Conjure can produce, and adding automatically the embellishments human experts use to enhance the performance of their models, such as symmetry breaking and implied constraints.


  There are three major facts that should be watched out for in all payday loans in the United States. They were lucky to produce Viagra Sublingual which dissolves under the tongue and penetrates into the blood causing erection faster than any other drugs.