Originally posted by: glebB
Dear Petr,
thank you for the hints. The example sched_square would have been very helpful in the beginning if the documentation had pointed out its existence. Here are the results: for "mutually exclusive" items the cumulative constraint is indeed sufficient. But the removal of the "or" did not change anything in the results.
Search strategy is indeed important. For difficult instances, in addition to separation of dimensions you spoke of, it is efficient to sort items by decreasing size/area or measure the failure rate:
IloSearchPhaseArray phaseArray(env);
IloVarSelectorArray varSelArray(env);
varSelArray.add(IloSelectSmallest(// 3, // mult selection is bad
IloVarSuccessRate(env)));
// varSelArray.add(IloSelectSmallest(3, IloDomainSize(env)));
// varSelArray.add(IloSelectSmallest(IloDomainMin(env)));
IloSearchPhase xPhase(env, X, // separation of dimensions is important!
varSelArray,
// IloSelectSmallest(IloVarSuccessRate(env)),
// IloDomainSize(env)), // X23 !
// IloVarIndex(env, X)),
IloSelectSmallest(IloValue(env))
);
phaseArray.add(xPhase);
IloSearchPhase yPhase(env, Y, varSelArray,
// IloSelectSmallest(IloVarSuccessRate(env)),
// IloDomainSize(env)), // X23: good
// IloVarIndex(env, Y)),
IloSelectSmallest(IloValue(env))
);
phaseArray.add(yPhase);
However, this more complicated search strategy seems to require pure integer variables which I had to produce like this:
IloIntVarArray X(env, m), Y(env, m);
for (int i=0;i<m;++i) {
X[i] = IloIntVar(env, 0, H-h[i]);
model.add(X[i] == IloStartOf(tasks1[i]));
Y[i] = IloIntVar(env, 0, W-w[i]);
model.add(Y[i] == IloStartOf(tasks2[i]));
}
Adding (IloCP::CumulFunctionInferenceLevel, IloCP::Extended) halved the number of branches in a difficult instance.
Best,
Gleb
#ConstraintProgramming-General#DecisionOptimization