We indeed can see by comparing the generated .cpo models is that the transition matrix generated by OPL differs from the one produced by the python model.
Thank you for the information, it helps us a lot.
Original Message:
Sent: Fri June 03, 2022 05:38 AM
From: Rustam Salikhov
Subject: CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1
Dear Renaud,
Thank you for your support. I hope it will be easy to fix it.
I wanted to continue the investigation and I've written the model using docplex (Python API). It was surprised me - the solution was correct. Maybe it can help you to investigate the reason of the solver behaviour when the model is written on opl.
Here my code:
import docplex.cp.model as cp_modelchanges = [[0, 0, 20], [0, 0, 0], [0, 0, 0]]mdl = cp_model.CpoModel("NoOverlap, transition matrix, isDirect=1")a = mdl.interval_var(name="a", size=5)b = mdl.interval_var(name="b", size=5)c = mdl.interval_var(name="c", size=5)seq = mdl.sequence_var(name="seq", vars=[a, b, c], types=[0, 1, 2])mdl.add(mdl.minimize(mdl.end_of(c)))mdl.add(mdl.no_overlap(seq, changes, True))mdl.add(mdl.start_before_start(a, b))mdl.add(mdl.start_before_start(b, c))msol = mdl.solve(trace_log=False)if msol is not None and msol.is_solution(): print("{}".format(msol.get_var_solution(a))) print("{}".format(msol.get_var_solution(b))) print("{}".format(msol.get_var_solution(c)))
Regards,
------------------------------
Rustam Salikhov
Original Message:
Sent: Thu June 02, 2022 10:23 AM
From: Renaud Dumeur
Subject: CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1
Dear Rustam,
It really looks like a bug happening when a single transition time is specified.
I've added an extra interval and a transition time of 1 to it, and with isDirect=true, we have a correct solution:
using CP;tuple changes_type{ int id1; int id2; int value; };{changes_type} changes = { <1, 3, 20>, <3,4,1> };//{changes_type} changes = { <1, 3, 20> };dvar interval a size 5;dvar interval b size 5;dvar interval c size 5;dvar interval d size 5;dvar sequence seq in append(a, b, c, d) types append(1, 2, 3, 4);minimize endOf(c);subject to {noOverlap(seq, changes, true);startBeforeStart(a, b);startBeforeStart(b, c);startBeforeStart(c, d); } execute { writeln("a", a); writeln("b", b); writeln("c", c); writeln("d", d); }
but note that a zero duration transition from c to d would trigger the bug again.
Thank you for notifying us.
Cheers,
------------------------------
Renaud Dumeur
Original Message:
Sent: Thu June 02, 2022 06:43 AM
From: Rustam Salikhov
Subject: CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1
Hi everyone,
I have found the situation when function noOverlap with flag isDirect=1 works incorrect. The solution should be a=[0, 5), b=[5, 10), c=[10, 15). But the model gives a=[0, 5), b=[5, 10), c=[25, 30) - as if I use isDirect=0.
It is a bug or maybe I'm doing smth wrong?
Model:
using CP;
tuple changes_type{ int id1; int id2; int value; };
{changes_type} changes = { <1, 3, 20> };
dvar interval a size 5;
dvar interval b size 5;
dvar interval c size 5;
dvar sequence seq in append(a, b, c) types append(1, 2, 3);
minimize endOf(c);
subject to {
noOverlap(seq, changes, true);
startBeforeStart(a, b);
startBeforeStart(b, c);
}
CPLEX version: 20.1.0.0
------------------------------
Rustam Salikhov
------------------------------
#DecisionOptimization