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

# Pinned topic constraint depends on dvar !!??

‏2013-10-25T22:30:59Z | consecutive constraint cplex

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

• ol
94 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

• 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
94 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

• 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 )

• ol
94 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