« JaCoP version 3.1 is released | Main | News from Google or-tools (CP solver) »

Global Constraint Seeker

Yesterday I visited Helmut Simonis' site (searching for another thing), and found this following announcement:

A Constraint Seeker

The global constraint catalog is a very useful resource for learning about all the different global constraints that have been decribed in the literature. But it can be challenging to find the right constraint, if you do not already know its name. Nicolas Beldiceanu and myself have been working on a web application which helps you find constraints in the catalog, given positive or negative examples. We have written a paper on this system, and a prototype is now running at Web Application. You may want to read Basic Help before entering your own queries.
Wow, that seems to be very interesting, and I just have to test it.

First some links, and after that some examples of Global Constraint Seeker in action. I haven't tested that many samples, but according to the paper it can handle many of the existing global constraint. However:
Most of the missing constraints use finite set variables or are graph constraints, which are not provided in the SICStus Prolog constraint engine.


The Constraint Seeker is written
in SICStus Prolog, integrated with an Apache web server. Nearly all of the HTML output is generated, the rest is fairly simple forms and css data. The Prolog code is just over 6,400 lines, developed over a period of 3 months by one of the authors. The six constraint models in the Seeker make up 2,000 lines, roughly one third of the code. This line count does not include the 50,000 lines of Prolog describing the constraints themselves.


From Summary and Future Work:
Besides introducing the Constraint Seeker, the key contribution of the paper is to illustrate the power of meta data and meta programming in the context of future constraints platforms.

....

The electronic version of the global constraint catalog provides such information in a systematic way for the different global constraints. The Constraint Seeker presented in this paper illustrates the fact that the same meta data can be used for different purposes (unlike ad-hoc code in a procedural language which is designed for a specific (and unique) usage and a single system).

Some examples

Here are some examples I've tried (played with) which may give a taste of what the Constraint Seeker can do. First are the three instances from the examples in Global Constraint Seeker: How to enter examples and how to interpret results. Note that I here just show the global constraints; there is much more information in the result, such as rank, density, links, etc which is left out.

p(5,7)

A search on p(5,7) means that we are looking for a global constraint with two arguments 5, and 7; p stands for a positive instance . What constraint (relation) is this?

The Seeker Matches (best matches) for p(5,7) is
  • lt
  • same_sign
  • leq
  • gt
  • geq
  • neq
Note that Constraint Seeker also detect global constraints where the order of arguments are swapped.

p(2,[4,2,4,5],4)

This is a slightly harder example: we are searching for three arguments, two scalar values (2 and 4) and the list [4,2,4,5].

A search on p(2, [4,2,4,5], 4) yields this Seeker Matches:
  • exactly
  • atleast
  • atmost
  • minimum_greater_than
  • int_value_precede
  • atmost
And the Wider Matches:
  • element
  • count
These "wider search" are found with some more and general transformation than "Seeker Matches".

p([[1,3,4,1],[2,9,11,2],[3,10,13,1],[6,6,12,1],[7,2,9,3]],8)

The first two queries was quite simple (for a human), but what constraint is p([[1,3,4,1],[2,9,11,2],[3,10,13,1],[6,6,12,1],[7,2,9,3]],8)?

Oh, it's a cumulative:
  • cumulative
  • cumulative_product
  • ordered_atmost_nvector
  • atmost_nvector
  • cumulative
  • coloured_cumulative
  • cumulative_product
  • coloured_cumulative
(Why two occurrences of cumulative, cumulative_product, etc are listed is explained in the paper.)

Below are some of my own tests, selected for different (and personal) reasons.

Looking for circuit

This test (searching for the circuit constraint) use a negative instance (n()) and three positive instances. 
p([2,4,5,3,6,8,1,7])
p([4,1,2,5,6,8,3,7])
p([6,4,2,5,1,8,3,7])
n([1,2,3,4,5,6,7,8])
In this case, the Seeker don't yield any "direct" matches, but found the following Wider matches:
  • circuit
  • derangement
  • derangement
Maybe more examples (positive and negative) would help?

p(3, [1,2,4,3,5,6,0,0,0,18,7], 0)

p(3, [1,2,4,3,5,6,0,0,0,18,7], 0)
  • exactly
  • atleast
  • atmost
  • atleast
  • int_value_precede
Wider matches:
  • count

Cumulative again: Furniture moving

In Marriott & Stuckey: "Programming with constraints" (page 112f) there is a problem how to schedule furniture moving. The MiniZinc model furniture_moving.mzn is one way of modeling this. The result is 
Durations  = array1d(1..4, [30, 10, 15, 15]);
EndTimes   = array1d(1..4, [60, 10, 30, 15]);
Resources  = array1d(1..4, [3, 1, 3, 2]);
Starts     = array1d(1..4, [30, 0, 15, 0]);
numPersons = 3;
Could Constraint Seeker find that this is a cumulative, and that it is valid? What happen if we change numPersons to 2 (i.e. an invalid solution)?

Let's test that. We have just a single positive instance where the order of the the variables are the same as above : p([30, 10, 15, 15], [60, 10, 30, 15], [3, 1, 3, 2], [30, 0, 15, 0], 3). Ah, it finds cumulative_product, and cumulative. Great.
  • cumulative_product
  • cumulative
  • cumulative
  • coloured_cumulative
  • coloured_cumulative
  • all_differ_from_at_least_k_pos
  • atleast_nvector
These constraints are found with use of the transformation T6.

Now, what will happen if we change number of person from 3 to 2: p([30,10,15,15], [60,10,30,15], [3,1,3,2], [30,0,15,0], 2)?

Well, it don't find cumulative_product or cumulative anymore, just
  • coloured_cumulative
  • coloured_cumulative
  • all_differ_from_at_least_k_pos
  • atleast_nvector
Hmm, I'm not really sure I understand all the consequences of this...

p([2,2,2,0,0,0,0], [0,1,2,3,4,5,6], [2,0,1,2,0,1])

I first tried it stated as p([2, 2, 2, 0, 0, 0, 0], [2, 0, 1, 2, 0, 1]) but the Seeker could not find it, probably since this form is not in the Global Constraint Catalog. Can you guess what this is? It's one of my favorite global constraints (no, it's not alldifferent_except_0 :-) .

However, stating it as p([2,2,2,0,0,0,0], [0,1,2,3,4,5,6], [2,0,1,2,0,1]) worked very well. Just a single result: the one I had in mind.

Summary and a comment

Even though I have just played little with Global Constraint Seeker I like it very much. And it's quite safe to say that I have not realized its fully potential.

The only thing I miss right now is that the Seeker should - if possible - give a message if there is a syntax error etc. E.g. for the erroneous query p(2,[4,2,4,5],4 (no right parenthesis) it just show ----end of run---.

[Now, why did I visit Helmut's site? Ah, his (& etc.) Using Constraint Visualization Tools (PDF). Great!]

Posted by hakank on May 29, 2011 09:27 AM |