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 is my code:
import docplex.cp.model as cp_model
changes = [[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