Hi Philippe,
I finally got some free time to work on this project again. So, I am now using the python API because it would be easier for me to automate the work and I also didn't like the syntax of cplex. I am sorry for the inconvenience if you don't have experience with python but the coding is pretty similar.
Below is a more realistic example of what I need and below it is the output. Now based on the way I understood your solution, what I need to do is create one dummy variable in the sequence. Make it last in the sequence. The set (start_of_next(sequence,interval) - start_of(interval)) %2 == 1 for every interval except dummy interval. This is exactly what this code does with (start_of_next(sequence,interval) - start_of(interval)) %2 == 1 disabled (the three commented lines). When I remove the comments, I will get solution unknown.
The reason I kept them commented is because I want to show you that last interval is showing as last in the sequence but it is starting before test_intervals_2 and test_intervals_3. Please let me know what I am doing wrong.
Edit: The code is refusing to be formatted for some reason when I do insert code. I'll have to put it unformatted.
from docplex.cp.model import CpoModel
timeout = 5
delay = 50
variables = ["t0", "t1", "t2", "t3", "t4"]
precedences = [
["t0", "t2"],
["t1", "t2"],
["t1", "t3"],
["t2", "t3"],
]
mdl = CpoModel()
# Intervals
test_intervals_start = mdl.interval_var_dict(variables,size=1, name="testIntervalsStart")
test_intervals_end = mdl.interval_var_dict(variables,size=1, name="testIntervalsEnd")
dummy_interval = mdl.interval_var(size=1,name="dummy")
# Intervals in list
all_interval_list = list(test_intervals_start.values()) + list(test_intervals_end.values()) + [dummy_interval]
interval_start_list = list(test_intervals_start.values()) + [dummy_interval]
# Sequence is start intervals + dummy interval
start_sequence = mdl.sequence_var(interval_start_list, name="start_sequence")
# No overlap
mdl.add(mdl.no_overlap(all_interval_list))
# precedences constraint
for p in precedences:
pre = p[0]
post = p[1]
mdl.add(mdl.end_before_start(test_intervals_end[pre],test_intervals_start[post]))
# end delayed 50 cycles after start
for v in variables:
mdl.add(mdl.start_at_start(test_intervals_start[v],test_intervals_end[v],delay))
# Dummy should be last in sequence
mdl.add(mdl.last(start_sequence,dummy_interval))
for v in variables:
cur_start = mdl.start_of(test_intervals_start[v])
next_start = mdl.start_of_next(start_sequence,test_intervals_start[v])
# mdl.add(mdl.end_before_start(cur_start,next_start))
dist = mdl.minus(next_start,cur_start)
# dist_mod2 = mdl.mod(dist,2)
# mdl.add(mdl.equal(dist_mod2,1))
# mdl.add(mdl.equal(dist,100))
#
mdl.add(mdl.minimize(mdl.max([mdl.end_of(i) for i in all_interval_list])))
msol = mdl.solve(TimeLimit=timeout)
print("Solution status: " + msol.get_solve_status())
print("Solve time: " + str(msol.get_objective_values()) + "s\n")
msol.write()
Solution status: Optimal
Solve time: (154,)s
-------------------------------------------------------------------------------
Model constraints: 11, variables: integer: 0, interval: 11, sequence: 2
Solve status: Optimal
Search status: SearchCompleted, stop cause: SearchHasNotBeenStopped
Solve time: 0.01 sec
-------------------------------------------------------------------------------
Objective values: (154,), bounds: (154,), gaps: (0,)
dummy: (start=2, end=3, size=1, length=1)
testIntervalsEnd_0: (start=51, end=52, size=1, length=1)
testIntervalsEnd_1: (start=50, end=51, size=1, length=1)
testIntervalsEnd_2: (start=102, end=103, size=1, length=1)
testIntervalsEnd_3: (start=153, end=154, size=1, length=1)
testIntervalsEnd_4: (start=53, end=54, size=1, length=1)
testIntervalsStart_0: (start=1, end=2, size=1, length=1)
testIntervalsStart_1: (start=0, end=1, size=1, length=1)
testIntervalsStart_2: (start=52, end=53, size=1, length=1)
testIntervalsStart_3: (start=103, end=104, size=1, length=1)
testIntervalsStart_4: (start=3, end=4, size=1, length=1)
start_sequence: (testIntervalsStart_1, testIntervalsStart_0, testIntervalsStart_4, testIntervalsStart_2, testIntervalsStart_3, dummy)
------------------------------
Topa Topa
------------------------------
Original Message:
Sent: Tue July 28, 2020 02:15 AM
From: Philippe Laborie
Subject: how to schedule even/odd time tasks
"I was doing something like (startof(t[i]) - startofPrev(s, t[i],0) ) %2 == 1. It was ordering it t1, t0, t3, t2 but the distance between t1 and t0 was even."
Really? Then it is a bug. The Prev/Next are the ones of the sequence in the solution, so if the solution is t[1], t[0], t[3], t[2], the the constraint for i=0 says:
(startOf(t[0]) - startOfPrev(s, t[0],0) ) %2 == 1, which means that the distance between the start of t[0] and the start of previous task t[1] should be odd.
Do you have an instance showing the problem. Could you post how to reproduce this solution?
[I slightly edited my last proposed formulation as the odd distance is between the consecutive 'start', not between 'end' of an interval and the 'start' of the next one.]
------------------------------
Philippe Laborie
Original Message:
Sent: Mon July 27, 2020 03:16 PM
From: Topa Topa
Subject: how to schedule even/odd time tasks
Yes, I don't care if t0 is before t1 or after t1. The only thing I care about is the start distance between consecutive tasks are odd (included in question) and my other conditions (not included in question). I can't post the code but the issue I had was basically that the order could be (t0, t1), (t2, t3) where the parenthesis means it could be any order. I was doing something like (startof(t[i]) - startofPrev(s, t[i],0) ) %2 == 1. It was ordering it t1, t0, t3, t2 but the distance between t1 and t0 was even.
I might have messed up somewhere. However, my current solution with isomorphism works. You are probably right that there is an impact on performance. I will give it another attempt next month as what I currently have is working.
>And by the way, in my formulation I assumed that you had to alternate odd/even in the delays whereas your problem seems easier: only odd delays after the first task, so the formation could be simplified to:
It might have been understood that way but I meant in the question that t0 starts at even (I don't care anymore), then t1 starts at even and so on. So, distance is always odd.
------------------------------
Topa Topa
Original Message:
Sent: Mon July 27, 2020 11:05 AM
From: Philippe Laborie
Subject: how to schedule even/odd time tasks
There is something I do not understand. The formulation with isomorphism also do not guarantee that t0 is before t1. It could be that, in the solution t1, is before t0, no ?
If the sequence is known in advance (t0 before t1 before t2 ...), then you do not need sequence variables or isomorphism, you can directly post the constraint that the delay is odd on the delay of the precedence constraint.
And by the way, in my formulation I assumed that you had to alternate odd/even in the delays whereas your problem seems easier: only odd delays after the first task, so the formation could be simplified to:
using CP;int n=10;dvar interval taskIntervals [i in 0..n] size 1;dvar sequence s in taskIntervals;subject to { noOverlap(s); forall(i in 0..n-2) { (endOfPrev(s, taskIntervals[i],0) == 0) => (startOf(taskIntervals[i]) % 2==0); // First task starts at even time // Then the delay between consecutive tasks should be odd ((startOfNext(s, taskIntervals[i],0)-endOf(taskIntervals[i])) % 2) == 1; } last(s, taskIntervals[n]); // taskIntervals[n] is a technical interval variable at the end of the sequence}
The advantage of this formulation (compared to the one with isomorphism) is that it do not introduce additional interval variables with a different semantics (the itvs[i]) which could have some impact on the performance of the resolution.
------------------------------
Philippe Laborie
Original Message:
Sent: Fri July 24, 2020 09:37 PM
From: Topa Topa
Subject: how to schedule even/odd time tasks
I got it working. The issue is that the constraints don't guarantee t0 is before t1. This means that I can get different position and declared position in the sequence which would make Prev or Next (which are based on position) output out of order.
What I used is the isomorphism constraint. Basically, this constraint does a 1-to-1 correspondence between two sets. The first set is my task set. The second set is an ordered task set. CPLEX will then force the first set to follow the same pattern as the second set during optimization.
{string} TaskNames = {t0,t1,t2,t3,t4,t5,t6,t7,t8,t9};dvar Interval taskIntervals [t in TaskNames] size 1;int n=10;range r=0..n-1;dvar interval itvs[r] size optional;subject to { // other constraints for taskIntervals forall(i in r : i!=0) { startBeforeStart(itvs[i-1],itvs[i]); (startOf(itvs[i])-startOf(itvs[i-1])) mod 2==1; } isomorphism(taskInverals, itvs);}
------------------------------
Topa Topa
Original Message:
Sent: Mon July 20, 2020 12:34 AM
From: Topa Topa
Subject: how to schedule even/odd time tasks
Hi,
Let's assume we have 10 tasks t0, t1, ... t9 for sake of simplicity and let's ignore dependency between tasks for sake of simplicity.
I have an OPL problem where I have to schedule the first task on an even time (0, 2, 4, 6, 8, ...). Second task must be after first task and odd time (1, 3, 5, ...). 3rd even, 4th odd, 5th even, and so on. First task won't necessarily be at 0 because there are actually other tasks.
If I can grab task Intervals sorted and then say something like Mod(t[i+1]-t[i+0],2) == 1 in the subject to that should work. How would I do something like that?
#DecisionOptimization