Hi everyone,

I have a scheduling problem in which each task processing sequence and its reverse sequence produce the same objective function value. In this problem, it is possible to eliminate some symmetries by arbitrarily setting one of the tasks to be performed in the first half of the task processing sequence. Would it be possible to make use of any feature of CP Optimizer to further explore this property of the problem?

Best regards,
M.

------------------------------
Martin
------------------------------

#DecisionOptimization

Hello,

usually, symmetries like this could be broken by an additional precedence. For example, if there are two tasks A and B that cannot overlap (because they require the same resource for execution) then constraint endBeforeStart(A, B) breaks the symmetry. A similar technique could be also used if A and B can overlap, however the constraint is weaker in this case: startBeforeStart(A, B) (alternatively it is also possible to use endBeforeEnd instead).

Best regards, Petr

------------------------------
Petr Vilím
IBM
------------------------------

Hello,

Thanks for your suggestion. It seems more effective than fixing an activity in the first half of the sequence.

Best regards,
Martin.

------------------------------
Martin
------------------------------

Original Message:
Sent: Wed July 01, 2020 05:27 AM
From: Petr Vilím
Subject: reverse sequence in a scheduling problem

Hello,

usually, symmetries like this could be broken by an additional precedence. For example, if there are two tasks A and B that cannot overlap (because they require the same resource for execution) then constraint endBeforeStart(A, B) breaks the symmetry. A similar technique could be also used if A and B can overlap, however the constraint is weaker in this case: startBeforeStart(A, B) (alternatively it is also possible to use endBeforeEnd instead).

Best regards, Petr

------------------------------
Petr Vilím
IBM
------------------------------