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

Pinned topic lexicographic constraint issues

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

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 ?

Thanks for your feedback

David

Attachments

  • AlexFleischer
    AlexFleischer
    77 Posts
    ACCEPTED ANSWER

    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

    3) If you add 

    y[10] in ypos;

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

    I hope this helps

    regards

     

     

     

  • AlexFleischer
    AlexFleischer
    77 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

    3) If you add 

    y[10] in ypos;

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

    I hope this helps

    regards