Topic
  • 5 replies
  • Latest Post - ‏2013-10-29T14:07:31Z by ol
5HNY_Imad_Abdeljaouad
6 Posts

Pinned topic constraint depends on dvar !!??

‏2013-10-25T22:30:59Z |

Hi,

I have a boolean dvar like this:

range i = 1..6;

dvar boolean x[i];

Let's say I would x to have only two values equal to 1 which I can do by adding this constraint:

sum(a in i) x[a] == 2;

I also would like to make sure that those two values that are equal to 1 must always come consecutively as in:

0 0 0 1 1 0 OR 1 1 0 0 0 0 OR 0 0 0 0 1 1 OR 0 1 1 0 0 0 ......etc

Thank you in advance,

  • ol
    ol
    62 Posts

    Re: constraint depends on dvar !!??

    ‏2013-10-28T10:28:11Z  

    Hello,

    In your case, an efficient approach would be using the constraint  IloAllowedAssignments, you just need to build an  IloIntTupleSet and to add to it the n-1 allowed tuples, where n is the number of variables (6 in your example).

    Regards,

    Olivier

     

  • 5HNY_Imad_Abdeljaouad
    6 Posts

    Re: constraint depends on dvar !!??

    ‏2013-10-28T12:42:02Z  
    • ol
    • ‏2013-10-28T10:28:11Z

    Hello,

    In your case, an efficient approach would be using the constraint  IloAllowedAssignments, you just need to build an  IloIntTupleSet and to add to it the n-1 allowed tuples, where n is the number of variables (6 in your example).

    Regards,

    Olivier

     

    Thank you but I am not using any programming language, is there any way I can do it using OPL???

    thanks,

  • ol
    ol
    62 Posts

    Re: constraint depends on dvar !!??

    ‏2013-10-28T13:45:47Z  

    Thank you but I am not using any programming language, is there any way I can do it using OPL???

    thanks,

     

    sure, you first define the set of tuples:


    Tuples = { <1,1,0,0,0,0>, <0,1,1,0,0,0>, ... };

    and then post the constraint:

    allowedAssignments(Tuples, x);

     

    Regards,

    Olivier

  • 5HNY_Imad_Abdeljaouad
    6 Posts

    Re: constraint depends on dvar !!??

    ‏2013-10-28T14:37:49Z  
    • ol
    • ‏2013-10-28T13:45:47Z

     

    sure, you first define the set of tuples:


    Tuples = { <1,1,0,0,0,0>, <0,1,1,0,0,0>, ... };

    and then post the constraint:

    allowedAssignments(Tuples, x);

     

    Regards,

    Olivier

    I see. Given that those numbers (range from 1..Nb which is 6 in the eg., and the number of consecutive 1s which is 2 in the eg.) can change based on what I have in the data file, it would be inefficient and would definitely make the model long/hard to write. Anyway, I just found a way (after days of thinking and trying):

    I use two expressions, one to store the index of the first '1' and another for the index of the last '1'.

    int Nb = 6;
    int j = 2;
     
    range i = 1..Nb;
     
    dvar boolean x[i];

    dexpr int ending = max(t in i) (x[t] * t);

    dexpr int starting = min(t in i) ( ( (-(x[t]*t)+t)*(2*Nb) )+t ); 

    //obj function here

     
    //constraints:
    subject to{
         sum(t in i) x[t] == j; //where j is how many 1s you would like to be consecutive , in the example above it's 2
     
         ending - starting ==  j -1;
    }

    //thanks to Joris Kinable (JorisK) for the ending constraint

    Of course I assume that j >= 2, otherwise there is no need to bother with the constraint (and it will not work :P )

    Updated on 2013-10-28T22:09:56Z at 2013-10-28T22:09:56Z by 5HNY_Imad_Abdeljaouad
  • ol
    ol
    62 Posts

    Re: constraint depends on dvar !!??

    ‏2013-10-29T14:07:31Z  

    I see. Given that those numbers (range from 1..Nb which is 6 in the eg., and the number of consecutive 1s which is 2 in the eg.) can change based on what I have in the data file, it would be inefficient and would definitely make the model long/hard to write. Anyway, I just found a way (after days of thinking and trying):

    I use two expressions, one to store the index of the first '1' and another for the index of the last '1'.

    int Nb = 6;
    int j = 2;
     
    range i = 1..Nb;
     
    dvar boolean x[i];

    dexpr int ending = max(t in i) (x[t] * t);

    dexpr int starting = min(t in i) ( ( (-(x[t]*t)+t)*(2*Nb) )+t ); 

    //obj function here

     
    //constraints:
    subject to{
         sum(t in i) x[t] == j; //where j is how many 1s you would like to be consecutive , in the example above it's 2
     
         ending - starting ==  j -1;
    }

    //thanks to Joris Kinable (JorisK) for the ending constraint

    Of course I assume that j >= 2, otherwise there is no need to bother with the constraint (and it will not work :P )

    ok, if this model fits your need it's fine.

    If the search for a solution is not so fast, you may want to try the model with allowedAssignments: it is complete for the propagation and will propagate much more. Note also that the number of  consecutive 1s does not impact the number of tuples which is always n. Nevertheless, if n is too large (n tuples of size n will give n^2 integers) there are different ways of improving this model.

    Regards,

    Olivier