My Constraint Programming Blog

Nicolas Beldiceanu and Helmut Simonis has written a very interesting paper about A Model Seeker, a system that finds the problem given a solution. Or more to the truth: suggests the appropriate global constraints given positive data instances (solution(s) to a certain problem). It was presented at the technical track of CP2012 (18th International Conference on Principles and Practice of Constraint Programming).

The system (A Model Seeker) is described in the paper: A Model Seeker: Extracting Global Constraint Models From Positive Examples (also: Presentation and Poster from the CP2012 conference).

From the Abstract:

We describe a system which generates finite domain constraint models from positive example solutions, for highly structured problems. The system is based on the global constraint catalog, providing the library of constraints that can be used in modeling, and the Constraint Seeker tool, which finds a ranked list of matching constraints given one or more sample call patterns.
We have tested the modeler with 230 examples, ranging from 4 to 6,500 variables, using between 1 and 7,000 samples. These examples come from a variety of domains, including puzzles, sports-scheduling, packing & placement, and design theory. When comparing against manually specified “canonical” models for the examples, we achieve a hit rate of 50%, processing the complete benchmark set in less than one hour on a laptop. Surprisingly, in many cases the system finds usable candidate lists even when working with a single, positive example.

A companion technical report presents the details of the 230 tested examples: A Model Seeker Description and Detailed Results (over 1400 pages).

This is a system I really would like to test...