Originally posted by: s.st1led
Thank you, if I replace the count/all by the sum of binary variables, then the model correctly states that the first problem is unfeasible, and the second is feasible returning a solution. From the correctness point of view there's no problem here, and I would be more than happy to use this solution you proposed.
However, I'm afraid that defining active_task as a sum of binary variables is very inefficient. Consider this final model:
using CP;
range T = 0..400;
range X = 0..200;
tuple Task {
key string id;
int duration;
}
tuple TaskExecution {
Task task;
int execution;
}
tuple TaskExecutionIndex {
TaskExecution task_execution;
int index;
}
{Task} J = {<"j0",2>, <"j1",3>};
{TaskExecution} A = {<j,x> | j in J, x in X};
{TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1};
dvar int task_executions[j in J] in T;
dvar int active[ap in AP] in T;
//1. dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
//2. dexpr int active_task[j in J, t in T] = sum(x in X, p in 0..j.duration-1) (active[<<j,x>,p>] == t && x < task_executions[j]);
dexpr int load[t in T] = sum(j in J) active_task[j, t];
subject to{
forall(t in T)
c1: load[t] == 1;
// c2: active[<<<"j0",2>,0>,0>] == 0;
// c3: active[<<<"j0",2>,0>,1>] == 1;
// c4: active[<<<"j1",3>,0>,0>] == 0;
// c5: active[<<<"j1",3>,0>,1>] == 3;
// c6: active[<<<"j1",3>,0>,2>] == 4;
//
// c7: task_executions[<"j0",2>] == 1;
// c8: task_executions[<"j1",3>] == 1;
}
Note that the task executions range now in X=0..200 and T ranges in 0..400. These numbers are similar to the instance of the problem I'm trying to solve, and from which I derived this minimal working example to show you this issue.
In this case, the alternative 1 for the definition of active_task leads to a model with 401 constraints (basically one for each t in T). If it would work, I think it would lead to a very efficient model, where the number of constraints is linear with respect to the size of T.
The second alternative you proposed instead, leads to a model of over 1 million constraints that CP Optimizier is barely able to load (and solve)! I guess, but that's only speculation since I'm not an expert about CP, that this is a common problem with CP when one has many binary variables (whose domain then it's only true-false): in this case the propagation and domain-reduction is quite inefficient. From this point of view, the first alternative with count/all would be much more preferable, but I'm not sure if it's meant to really work with variable ranges. If not then, why does it compile and has such an inconsistent behavior?
Regards,
Stefano
#DecisionOptimization#OPLusingCPOptimizer