Originally posted by: SystemAdmin

Hi everybody, I have some problems understanding how constraining a sum with a variable range works. Suppose you have the following constraint satisfaction problem:

using CP;   range T = 1..4;   dvar 

int x in T; dvar 

int y in T; dvar 

int z[t in T] in 0..1;   subject to 
{ c:  sum(t in x..y) z[t] == 1; 
}

The following assignment of variables should be a solution for the problem (though many others are feasible as well):

x=1, y=1, z=[1,0,0,0]

If I let the above code run in CP, it reports that the model has no solution. Why is that? Meanwhile, changing the right hand side of the equality constraint c from 1 to 0 makes CP find the solution

x=1, y=1, z=[0,0,0,0]

which is just fine.

Any ideas?

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
The following syntax is not supported by OPL:

dvar 

int x in T; dvar 

int y in T; ... subject to 
{ sum(t in x..y) z[t] == 1;

You cannot use decision variables in an aggregator like sum. This being said, OPL should give an explicit error in this case.
I'm not sure what you want to model.

If you want to sum up all z in T, you should do:

subject to 
{ sum(t in T) z[t] == 1; 
}

If you want to sum up only the z with index in [x,y], you could do something like (many variants are possible):

dvar 

int x in T; dvar 

int y in T; ... subject to 
{ sum(t in T) ((z[t]==1) && (x<=t) && (t<=y)) == 1; 
}

If x and y are the start and end time of some activity (assuming you are modeling a scheduling problem and T is the time-scale), you could also consider using interval variables in CP Optimizer.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Thank you for your help. Indeed I was deceived by OPL not giving me any compile-time error, so I thought the syntax was allowed. Plus, the case with 0 worked so I thought this syntax was supported. Your second suggestion is what I'm looking for: summing only the z's in the interval x,y. I've never seen such a syntax in OPL: I find it a bit counterfactual since it puts a boolean condition for the index of the sum outside its definition scope (I would have expected indeed something like I wrote with the semicolon after t). That said, I tried it and it works just fine, so again thank you!

Could you please tell me something about the other possible variants you mentioned? I'm solving a problem in which the computing performance matters, and I'd like to know which is the most performing alternative. I tried looking in the guide, but there I can find only straightforward examples, while this sum in a variable range seems to require some advanced tricks like the one you posted.

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
There is nothing tricky in the syntax:

sum(t in T) ((z[t]==1) && (x<=t) && (t<=y)) == 1;

For a given t in T, ((z[t]==1) && (x<=t) && (t<=y)) is an integer (boolean) expression; you can sum up integer expressions, this gives an integer expression and you post the constraint that this expression is equal to 1.

What is not allowed in the OPL syntax is to use non-ground integer expressions or decision variables in the scope of the sum, max, min.

Possible variant (but very close) is:

sum(t in T) minl(z[t], (x<=t), (t<=y)) == 1;

If [x,y] represents an interval of time (for instance an activity) and the domain of T is very large, you may also consider modeling [x,y] as an interval variable:

dvar interval act in T;

If you can leverage the scheduling concepts (constraints, expressions) provided in OPL around interval variables to avoid an explicit enumeration of time (t in T), that can result in a very efficient model. For a description of those scheduling concepts, have a look at this section of the documentation:

IDE and OPL > Optimization Programming Language (OPL) > Language Reference Manual > OPL, the modeling language > Scheduling

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

I see: I didn't know that in CP you can handle integer and boolean expression in the same way. This basically allows summing boolean expressions, something that some other languages I know like Java or C# don't allow. Thank you for your suggestion using intervals. I have been using them for other purposes, but didn't think that they could have also fit for this situation. I will try them as well and in case ask a more specific question.

Since both of your non-interval proposals work, I mark this question as answered and thank you for your help.

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer