Topic
• Latest Post - ‏2014-03-11T17:40:24Z by davidoff
davidoff
51 Posts

# Pinned topic lexicographic constraint issues

‏2014-03-10T22:34:30Z | lex

Hello

I'm trying to establish constraints that will order a set of triplet of variables. Think of ordering people by age, wealth and id for instance, in this lexicographic order. Therefore, I will create array for ages, wealths and instance , indexed by anonymous people and then create one lex constraint to compare the first people triplet of variables with the next people set, and so on. I attached a sample where a range P plays the role of people and I have two criteria instead of three. I have several questions for that matter :

1) is the lex constraint a good way to model this total ordering ? I was thinking that sometimes, I may have ties. For instance, with two criteria only, it could happen that for some reasons the two arrays have exactly the same values but this assignment seems to be forbidden by the lex constraint. However, this could be worked around adding a third variable to each pair and set the first one to 0 and the second one to 1 for instance, so that the lex constraint on the array of three variables will always be true even if we have tie on the two first criterias.

2) In OPL, it is valid to define an array of two variables in extension such as

dvar int xy1[1 .. 2] = [x[1] ,y[1] ];//ok

However I did not manage to write this for an array of p variables, such as :

dvar int xy2[P][1..2] = [p : [x[p], y[p]] | p in P];//error
dvar int xy3[p in P][1..2] = [x[p], y[p]];//error

Yet it is still possible to write :

dexpr int xy4[p in P][i in 1 .. 2] = (i==1 ? x[p] : y[p]);

but this is not fancy and furthermore not valid with the lex constraint that works on dvar, not on dexpr. So I had to define an additional variable tmp such as :

dvar int tmp[P][two];//an array to store x[p], y[p]

constraints{

tmp[p][1] == x[p];
tmp[p][2] == y[p];
}

so that I'm able to set the lex constraint on any consecutive arrays tmp :

forall(p in P : p<10){
lex( all(i in two) tmp[p][i] , all(i in two) tmp[p+1][i] );

}

Is there a way to avoid the tmp variable and work directly with x and y ? I guess the append keyword would avoid that but I would rather use a syntax such as xy1

3) Now, running this tiny example gives me unexpected results :

// solution
y = [0 0 0 0 0 0 0 0 0 -2147483647];
tmp = [[0 0]
[0 0]
[0 0]
[0 0]
[0 0]
[0 0]
[0 0]
[0 0]
[0 0]
[0 0]];
x = [0 0 0 0 0 0 0 0 0 0];

For me, results are awkward :

1. y is set to 0 for p=0 until 9 and y10 is a kind of NaN, while any y should be in the set 0,90,120
2. the tmp values are all identical [0, 0] so it seems that the lex constraint is never respected

Am I missing something in the understanding of lex , and how come y values are not in the domain ?

David

#### Attachments

• AlexFleischer
245 Posts

#### Re: lexicographic constraint issues

‏2014-03-11T08:57:01Z

Hi

lex:

The lexicographic constraint states that the first array of variables is less than or equal to the second array of variables in the lexicographic order.

1) No issue with ties since lex is less than or equal

For example:

int a1[1..2]=[1,2];
int a2[1..2]=[1,2];
int a3[1..2]=[1,3];

assert lex(a1,a2);
assert lex(a2,a3);

assert !lex(a3,a1);

execute
{
writeln(a1,a2,a3)
}

2) I would use append

y[10] in ypos;

in the constraint block then you do not get the strange value any longer.

I hope this helps

regards

• AlexFleischer
245 Posts

#### Re: lexicographic constraint issues

‏2014-03-11T08:57:01Z

Hi

lex:

The lexicographic constraint states that the first array of variables is less than or equal to the second array of variables in the lexicographic order.

1) No issue with ties since lex is less than or equal

For example:

int a1[1..2]=[1,2];
int a2[1..2]=[1,2];
int a3[1..2]=[1,3];

assert lex(a1,a2);
assert lex(a2,a3);

assert !lex(a3,a1);

execute
{
writeln(a1,a2,a3)
}

2) I would use append

y[10] in ypos;

in the constraint block then you do not get the strange value any longer.

I hope this helps

regards