Originally posted by: SystemAdmin

Hi,

I would like to get some help regarding the propagation of constraints in the Java API for CP. In order to explain my problem, I have a very trivial example to show the problem that I have encountered using the propagate method. In this example, I have two intervals that resembles two different tasks with different duration. The tasks share a common resource, so a cumulative function is used to book and unbook the resource during the different intervals. The objective is to minimize the time to perform the task. In the optimal schedule, the intervals are placed in a sequence. A different order of the tasks would result in the same ending time.

The method sortIntervals() below is a method that sorts the intervals according to start time. If I want to create a constraint to check if the latter task may start during the execution of the previous task and propagate this constraint, I should of course get an answer saying that the problem is infeasible since the tasks share a resource. However, if I use stepAtStart and StepAtEnd for when to book and unbook the resource, this is not the case. The answer is feasible, however I get a warning saying that "not all intervals have been placed". If I instead use a pulse function to book the resource, i.e I use r.add(cp.pulse(interval[j], 1)), I get an infeasible solution. Why can't propagate handle this booking/unbooking of the resource when it is modeled as below?

In this case I could use the pulse function instead, but for other examples, when a resource is supposed to be booked throughout several intervals, the pulse function may not be used.

So to summarize, my questions are: Why doesn't propagate return false in this example? How can I model the resource booking throughout several intervals and get a correct answer using propagate?

Example:

IloCP cp = new IloCP();
List<IloIntervalVar> sortedInterval = new ArrayList<IloIntervalVar>();
IloIntervalVar[] interval = new IloIntervalVar[2];
IloIntExpr[] ends = new IloIntExpr[2];
int] duration = new int[{2,3};
IloCumulFunctionExpr r = cp.cumulFunctionExpr();

for (int j=0; j<interval.length; j++){
interval[j] = cp.intervalVar(duration[j], Integer.toString(j));
sortedInterval.add(interval[j]);
ends[j] = cp.endOf(interval[j]);
r.add(cp.stepAtStart(interval[j], 1));
r.sub(cp.stepAtEnd(interval[j], 1));
}
cp.add(cp.le(r, 1));
cp.add(cp.minimize(cp.max(ends)));
if (cp.solve()){
System.out.println("Solution with objective: \t" + cp.getObjValue());
for(int j=0; j<interval.length; j++){
System.out.println("Interval: " + interval[j].getName() + " Start: " + cp.getStart(interval[j]) + " End: " + cp.getEnd(interval[j]));
}
}

sortIntervals(0, sortedInterval.size() - 1);

//Create a constraint stating that the start of the second interval should be during the execution of the first interval
IloIntExpr start_a = cp.startOf(sortedInterval.get(0)); //Start of first interval
IloIntExpr end_a = cp.endOf(sortedInterval.get(0)); //End of first interval
IloIntExpr start_b = cp.startOf(sortedInterval.get(1)); //Start of second interval

IloConstraint c1 = cp.lt(start_b, end_a); //Constraint stating that the start of the second interval should be less than the end of the first interval
IloConstraint c2 = cp.gt(start_b, start_a); //Constraint stating that the start of the second interval should be greater than the start of the first interval
cp.add(c1);
cp.add(c2);
System.out.println(cp.propagate());
Anyone who might be able to answer these questions?

Thanks in advance,
sundstrn
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,
Unlike function "solve()", The function "propagate()" does not look for a solution of the model. It just performs some inference at the root node to reduce the domain of variables. As such, if "propagate()" results in some variable domain being empty, it can deduce that the model is infeasible. But of course the opposite is not true: a model can be infeasible and still, "propagate()" may not be able to find it is infeasible. In order to prove that a model is infeasible you cannot rely on the "propagate()" function, you need to run a full "solve()".
Furthermore, depending on the formulation of the model, the result of "propagate()" may be different because some models may result in more constraint propagation than others. In your case, when you replace a pair +stepAtStart-stepAtEnd by a +pulse, the resulting model results in stronger constraint propagation because the engine will reason on a single pulse expression that represents the conjunction of too apparently independent ones (stepAtStart and stepAtEnd). This explains why you may find more infeasibilities with the model using "pulse". You will find more infeasibilities but of course not all of them.
One thing not directly related to your question: if you want to add precedence constraints to your model, it is better to directly use constraints between interval variables (like endBeforeStart, startBeforeStart, etc.) rather than arithmetical constraints on start/endOf expressions.
Hope it helps,
Philippe
#ConstraintProgramming-General
#DecisionOptimization