[Coin-standards] Technical Item! CLP

[Irv Lustig]

At 11:52 AM 4/11/02 -0500, Leonardo B. Lopes wrote:
>So what would be a good way of representing *instances* of CLP problems?
>Where do they become models?

It's a model when there is no data associated with the problem.

It becomes an instance when you unroll "forall" or other looping constructs 
and plug in the data.

For example, using OPL, let's say that I have a vector of 100 integers, and 
for each group of 10, I wanted to state an "alldifferent" constraint.  The 
OPL model would be:

var int x[0..99] in 0..100;
solve {
    forall (i in 0..9) {
       alldifferent (all(j in [i*10 .. i*10+9]) x[j]);
    }
};

A potential instance representation (using a bastardized OPL) is:

var int x[0..99] in 0..100;
solve {
    alldifferent ({x[0],x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8],x[9]};
    alldifferent ({x[10],x[11],x[12],x[13],x[14],x[15],x[16],
                   x[17],x[18],x[19]};
    /* etc. */
    alldifferent ({x[90],x[91],x[92],x[93],x[94],x[95],x[96],
                   x[97],x[98],x[99]};
};

The unrolling of the loops makes it much harder to see what the real model is.



>More specifically:
>
>Is it sufficient to represent CLP instances as Non-linearities? Can we
>define a few functions (cumulative, etc...) and then have a closed
>representation for CLP?

I think you can do this, but it won't be just a "few" functions.


>Do we need to have an extension mechanism?

Most likely.  People invent new constraints all the time, and you want to 
let people do that in an instance.


>Could people sketch (brainstorm quality sketch) what the characteristics
>of the representation should be?

I'll back out of that and let people who are real CP people respond.

         -Irv