Or-tools: Possible bugs on shift_scheduling_sat.py example

[stradivari96]

I think

for start in range(len(works) - length - 1):

should be

for start in range(len(works) - length + 1):

https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py#L95

For a list of length 4 the possible sequences of length 2 are:

[1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 1, 1]

The last start is 2 -> range(4-2+1) -> range(3) -> [0, 1, 2]

There are many lines where this appears, so maybe I am wrong.

Could test it and send a pull request.

[lperron]

It is a start, if the length is 2, the last element is 2 + 2 - 1, which is
the index of the last element in a zero based array of size 4.

Am I wrong?
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mer. 3 juil. 2019 à 23:58, Xiang Chen [e-mail] a
écrit :

I think

for start in range(len(works) - length - 1):

should be

for start in range(len(works) - length + 1):

https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py#L95

For a list of length 4 the possible sequences of length 2 are:

[1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 1, 1]

The last start is 2 -> range(4-2+1) -> range(3) -> [0, 1, 2]

There are many lines where this appears, so maybe I am wrong.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1399?email_source=notifications&email_token=ACUPL3JISARHOV3FNWESOM3P5UOIPA5CNFSM4H5MEDDKYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4G5HUJ7A,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3NTPRAX2TACAW3M553P5UOIPANCNFSM4H5MEDDA
.

[stradivari96]

Didn't understand the last message very well, but right now given a list of length 4 and a sequence length of 2, the line:

for start in range(len(works) - length - 1):

will only iterate through range(4-2-1) which is range(1) == [0] when I think it should return range(3) == [0, 1, 2] as the last sequence starts at index 2.

Not sure where the first 2 in 2 + 2 - 1 comes from.

[lperron]

Actually, both are wrong

you have 4 variables

v0, v1, v2, v3

You want to forbid sequence of exactly 2 true variables, you need to
construct 3 forbidden patterns

v0=true, v1=true, v2=false
v0=false, v1=true, v2=true, v3=false
v1=false, v2=true, v3=true

The negated bounded span takes care of adding the var=false to the pattern,
so the valid starts are 0, 1, 2. Therefore, both +1 and -1 are wrong.

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le jeu. 4 juil. 2019 à 10:58, Xiang Chen [e-mail] a
écrit :

Didn't understand the last message very well, but right now given a list
of length 4 and a sequence length of 2, the line:

for start in range(len(works) - length - 1):

will only iterate through range(4-2-1) which is range(1) == [0] when I
think it should return range(3) == [0, 1, 2], not sure where the first 2
in 2 + 2 - 1 comes from.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1399?email_source=notifications&email_token=ACUPL3JQLDGX76ST5Z4POWTP5W3TVA5CNFSM4H5MEDDKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZGZRAI#issuecomment-508401793,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3OZWNKIUAIRSAP4V7DP5W3TVANCNFSM4H5MEDDA
.

[lperron]

Thanks for the report. I have fixed the example on master.

[stradivari96]

I still think it should be +1 though.

You want to forbid sequence of exactly 2 true variables, you need to construct 3 forbidden patterns

Therefore range(3) instead of range(2) to iterate 3 times right? Do not forget that range generates the list [0, arg) arg not included. range(3) == [0, 1, 2]

Btw, this line also has the same problem:

https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py#L101

Thanks for taking a look!

[lperron]

you are right.

[lperron]

And line 115 too I suppose.

[stradivari96]

Yeah, maybe even:

https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py#L126

# Just forbid any sequence of true variables with length hard_max + 1
for start in range(len(works) - hard_max - 1):

This one I actually think is neither +1 nor -1, as the length we are forbidding is hard_max+1 so
for start in range(len(works) - hard_max): should work

[bcaessens]

After 1 year I don't want to create more confusion,

but I think Laurent was right in his first answer: neither -1 or +1 are needed. I was looking into negated_bounded_span to adapt it to other types of sequences when I came across this issue.

I think @stradivari96 erroneously used the hard_min in Laurent's example to start from, whereas you need to take the length variable in the code for the range. Let me clarify based on the example:

you have 4 work variables and you want to forbid sequences with a hard_min of 2.

w = [var0, var1, var2, var3] #with len(w) == 4 and indexes [0,1,2,3]

The restriction on the hard_min is a double loop:

for length in range(1, hard_min):
 for start in range(len(works) - length + 1):
                self.model.AddBoolOr(self.negated_bounded_span(works, start, length))

so, length will be in [1,2[ -> so in this case effectively just 1
(because negated_bounded_span adds another element to the end (beginning) as needed)

so start in range(len(w) - length + 1) in this case gives -> 4 - 1 + 1.
Meaning the loop runs 4 times over indexes 0 1 2 3 which is not what we want.
So I do think it should really be:

start in range(len(works) - length).

as Laurent pointed out.

Cheers,
Bernie.

[stradivari96]

If you remove the +1 this returns OPTIMAL instead of INFEASIBLE for [_, _, 0, 1]

from ortools.sat.python import cp_model


def negated_bounded_span(works, start, length):
    sequence = []
    # Left border (start of works, or works[start - 1])
    if start > 0:
        sequence.append(works[start - 1])
    for i in range(length):
        sequence.append(works[start + i].Not())
    # Right border (end of works or works[start + length])
    if start + length < len(works):
        sequence.append(works[start + length])
    return sequence


if __name__ == "__main__":
    model = cp_model.CpModel()
    works = [model.NewBoolVar("") for i in range(4)]

    for length in range(1, 2):
        for start in range(len(works) - length + 1):
            model.AddBoolOr(negated_bounded_span(works, start, length))

    model.Add(works[2] == 0)
    model.Add(works[3] == 1)

    solver = cp_model.CpSolver()
    solver.Solve(model)

    print(solver.StatusName())

[bcaessens]

Obviously you're right. So what I missed is that you need 4 boolOr's to express the 3 assignments we don't want! As in this example the length is always 1 it adds

or(works[0].Not, works[1])
or(works[0],works[1].Not,works[2])
or(works[1],works[2].Not,works[3])
or(works[2],works[3].Not)

setting 2 to 0 and 3 to 1 makes the last one fail! But, I was confused, as I thought we only forbid sequence < hard_min or 2, so in effect, a sequence of length 2 would be ok? Clearly, 1 1 0 1 would pass no?

Anyway, this probably does not belong in github, but on google groups I think. Sorry for the misposting.
Bernie

[stradivari96]

Hmm, I think hard min 2 means that sequences of ones have to have length >= 2.

So 1 1 0 1 does not pass because the first sequence of ones is correct but the second sequence (last single 1) is too short. Anyway, this actually depends on the definition of your constraint, maybe in your case you don't mind having a shorter sequence at the end of the list or something like that.

PS: I think is kinda okay to discuss this here as it is related to the issue, but if not, sorry for the spam Laurent/Mizux

[lperron]

Just send me a PR to correct the example if it is wrong :-)
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 8 sept. 2020 à 13:07, Xiang Chen [e-mail] a
écrit :

Hmm, I think hard min 2 means that sequences of ones have to have length

= 2.

So 1 1 0 1 does not pass because the first sequence of ones is correct
but the second sequence (last single 1) is too short. Anyway, this actually
depends on the definition of your constraint, maybe in your case you don't
mind having a shorter sequence at the end of the list or something like
that.

PS: I think is kinda okay to discuss this here as it is related to the
issue, but if not, sorry for the spam Laurent/Mizux

—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1399#issuecomment-688796195,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/ACUPL3IIC66P27E6FQNYJJLSEYF5VANCNFSM4H5MEDDA
.

[bcaessens]

Thanks everyone. So nothing to correct :-)

You are right of course, over the whole array we need all sequences of True booleans to be at least 2 (so >= 2). So indeed, the solution would be wrong because it contains the 01 in the end.

Somehow all of this makes more sense now. So thx for your time.

[qtbgo]

Hi, we still have a problem. Suppose the planning horizon is one week, that is 7 days. And suppose hard_min is 2 for a shift.
Then pattern 1000001 is in fact valid. Because the firt 1 can be combined with the last week's end 1. And the last 1 can be combined with the next week's first 1. But this pattern is considered invalid in the cp-sat model. Any idea?

[stradivari96]

This should work:

1. Remove the hard constraint for 0 and 6:

for length in range(1, hard_min):
    for start in range(len(works) - length + 1):
        if start == 0 or start == length-1:
            continue
        model.AddBoolOr(negated_bounded_span(works, start, length))

1. Forbid patterns manually:

10xxxx0: or(not(x[0]), x[1], x[6])
0xxxx01: or(x[1], x[5], not(x[6]))

[qtbgo]

Great, it works. Thiank you Xiang Chen. Have you ever test ortools in large employee Scheduling problem. For example 200 employees, 10 shifts, 30 days, or maybe with 30 skills. How is the performance of ortools in this regard?

[bcaessens]

We use it for 280 employees, 7-10 shift types, 28 weeks/7 days. No skills, but lot’s of other constraints. Performance wise, it is running pretty fast. Usually spitting out feasible solutions in about 20-60 minutes. Probably more solutions can be found, but we see the objective is not improving a lot (looks like saturation in neural networks...).
As to your problem, we solved it by putting constraints on a one-dimensional array of shifts over days. In that case, your sunday1 and monday 2 sit next to each other and the negated_bounded_span works as intended.

[qtbgo]

Thank you bcaseesns. I myself just tested it. I have 160 employees, 4 shift, 4 weeks. No other constraints. I build a MIP formulation for the problem to compare. The mip is solved by cplex to optimal in 40s with an objective 1040. While the or-tools' result is as follows:
Solution 0, time = 3.16 s, objective = 13452
Solution 1, time = 4.61 s, objective = 13415
Solution 2, time = 5.90 s, objective = 13404
......
Solution 302, time = 300.48 s, objective = 2496
Solution 303, time = 301.70 s, objective = 2450
Solution 304, time = 303.04 s, objective = 2430
Solution 305, time = 305.01 s, objective = 2410
........
Solution 390, time = 591.51 s, objective = 1145
Solution 391, time = 614.67 s, objective = 1136
Solution 392, time = 616.59 s, objective = 1133
Solution 393, time = 638.46 s, objective = 1124
.........
Solution 410, time = 8482.04 s, objective = 1061
Solution 411, time = 10451.73 s, objective = 1058

[lperron]

Do you use multiple workers for cp-sat ?

Le mar. 20 oct. 2020 à 11:08, qtbgo [e-mail] a écrit :

Thank you bcaseesns. I myself just tested it. I have 160 employees, 4
shift, 4 weeks. I build a MIP formulation for the problem to compare. The
mip is solved by cplex to optimal in 40s with an objective 1040. While the
or-tools' result is as follows:
Solution 0, time = 3.16 s, objective = 13452
Solution 1, time = 4.61 s, objective = 13415
Solution 2, time = 5.90 s, objective = 13404
......
Solution 302, time = 300.48 s, objective = 2496
Solution 303, time = 301.70 s, objective = 2450
Solution 304, time = 303.04 s, objective = 2430
Solution 305, time = 305.01 s, objective = 2410
........
Solution 390, time = 591.51 s, objective = 1145
Solution 391, time = 614.67 s, objective = 1136
Solution 392, time = 616.59 s, objective = 1133
Solution 393, time = 638.46 s, objective = 1124
.........
Solution 410, time = 8482.04 s, objective = 1061
Solution 411, time = 10451.73 s, objective = 1058

—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1399#issuecomment-712708439,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/ACUPL3NUJ3ZMRP4KL5F5PG3SLVHQNANCNFSM4H5MEDDA
.

[qtbgo]

employeeScheduling2.zip
this is the cp-sat model file. it use 8 workers.

[qtbgo]

if you comment Shift constraints, then or-tools solve to optimal in 4s. So, it seems that we need to find a way to improve Shift constraints.

[lperron]

Can you send us the MP model ?
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mer. 21 oct. 2020 à 01:20, qtbgo [e-mail] a écrit :

if you comment Shift constraints, then or-tools solve to optimal in 4s.
So, it seems that we need to find a way to improve Shift constraints.

—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1399#issuecomment-713194005,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/ACUPL3JATYWPWUFK7RTKFJDSLYLKLANCNFSM4H5MEDDA
.

[qtbgo]

OPLmodel.zip
this the cplex opl model and dat file for your reference.

[lperron]

But the OPL model is trivial. There are no complex constraints at all, no
sequence, no transition.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 26 oct. 2020 à 14:46, Mizux [e-mail] a écrit :

Assigned #1399 https://github.com/google/or-tools/issues/1399 to
@lperron https://github.com/lperron.

—
You are receiving this because you were assigned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1399#event-3920792233, or
unsubscribe
https://github.com/notifications/unsubscribe-auth/ACUPL3JAWDL23JWUV6E7WX3SMV4UPANCNFSM4H5MEDDA
.

[qtbgo]

I uploaded ortools model: employeeScheduling2.zip , and Opl model OPLmodel.zip. I ommited some same constraints in both models, so they are consistent. The opl moel is as follows. You see it has Shift constraints (sequence) which I think is most complex and slowest.
subject to {

// Exactly one shift per day.
forall(e in employee, d in days)
sum(s in shift)x[e][d][s] == 1;

// Shift constraints
forall(ct in shift_constraint){
forall(e in employee, b in 1..ct.hard_min-1, d in 1..numDay-(b+1))
x[e][d][ct.shift]+ sum(i in 1..b)(1-x[e][d+i][ct.shift]) + x[e][d+b+1][ct.shift] >= 1; //hard_min

forall(e in employee, b in 1..ct.soft_min-1, d in 1..numDay-(b+1))
x[e][d][ct.shift]+ sum(i in 1..b)(1-x[e][d+i][ct.shift]) + x[e][d+b+1][ct.shift] >= 1-underCon[ct][e][b][d]; //soft_min

forall(e in employee, d in 1..numDay-ct.hard_max)
sum(i in 0..ct.hard_max)x[e][d+i][ct.shift]<=ct.hard_max; //hard_max

}

// Weekly sum constraints
forall(ct in weekly_sum_constraint: ct.soft_min>ct.hard_min && ct.min_penalty>0)
forall(e in employee, w in week){
sum(d in w7-6..w7)x[e][d][ct.shift] >= ct.hard_min;
sum(d in w7-6..w7)x[e][d][ct.shift] >= ct.soft_min-underMinShift[ct][e][w];
}

forall(ct in weekly_sum_constraint: ct.soft_max < ct.hard_max && ct.max_penalty > 0)
forall(e in employee, w in week){
sum(d in w7-6..w7)x[e][d][ct.shift] <= ct.hard_max ;
sum(d in w7-6..w7)x[e][d][ct.shift] <= ct.soft_max + overMaxShift[ct][e][w];
}

// Penalized transitions

// Cover constraints
forall(w in week, d in 1..7, s in shiftWorking){
sum(e in employee)x[e][(w-1)7+d][s] >= weekly_cover_demand[d][s];//-underCover[w][d][s];
sum(e in employee)x[e][(w-1)7+d][s] <= weekly_cover_demand[d][s] + overCover[w][d][s];
}

}

[lperron]

I am not sure it is valid

forall(e in employee, b in 1..ct.hard_min-1, d in 1..numDay-(b+1))
x[e][d][ct.shift]+ sum(i in 1..b)(1-x[e][d+i][ct.shift]) +
x[e][d+b+1][ct.shift] >= 1; //hard_min

10111 , hard_min = 2

I believe it is an accepted start of the sequence.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 9 nov. 2020 à 14:41, qtbgo [e-mail] a écrit :

I uploaded ortools model: employeeScheduling2.zip , and Opl model
OPLmodel.zip. I ommited some constraints in these two models, but they are
consistent. The opl moel is as follows. You see it has Shift constraints
(sequence) which I think is most complex and slowest.
subject to {

// Exactly one shift per day.
forall(e in employee, d in days)
sum(s in shift)x[e][d][s] == 1;

// Shift constraints
forall(ct in shift_constraint){
forall(e in employee, b in 1..ct.hard_min-1, d in 1..numDay-(b+1))
x[e][d][ct.shift]+ sum(i in 1..b)(1-x[e][d+i][ct.shift]) +
x[e][d+b+1][ct.shift] >= 1; //hard_min

forall(e in employee, b in 1..ct.soft_min-1, d in 1..numDay-(b+1))
x[e][d][ct.shift]+ sum(i in 1..b)(1-x[e][d+i][ct.shift]) +
x[e][d+b+1][ct.shift] >= 1-underCon[ct][e][b][d]; //soft_min

forall(e in employee, d in 1..numDay-ct.hard_max)
sum(i in 0..ct.hard_max)x[e][d+i][ct.shift]<=ct.hard_max; //hard_max

}

// Weekly sum constraints
forall(ct in weekly_sum_constraint: ct.soft_min>ct.hard_min &&
ct.min_penalty>0)
forall(e in employee, w in week){
sum(d in w7-6..w7)x[e][d][ct.shift] >= ct.hard_min;
sum(d in w7-6..w7)x[e][d][ct.shift] >=
ct.soft_min-underMinShift[ct][e][w];
}

forall(ct in weekly_sum_constraint: ct.soft_max < ct.hard_max &&
ct.max_penalty > 0)
forall(e in employee, w in week){
sum(d in w7-6..w7)x[e][d][ct.shift] <= ct.hard_max ;
sum(d in w7-6..w7)x[e][d][ct.shift] <= ct.soft_max +
overMaxShift[ct][e][w];
}

// Penalized transitions

// Cover constraints
forall(w in week, d in 1..7, s in shiftWorking){
sum(e in employee)x[e][(w-1)7+d][s] >=
weekly_cover_demand[d][s];//-underCover[w][d][s];
sum(e in employee)x[e][(w-1)7+d][s] <= weekly_cover_demand[d][s] +
overCover[w][d][s];
}

}

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1399#issuecomment-724020243,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/ACUPL3NZDFST4MMZXUJGUTDSO7WP3ANCNFSM4H5MEDDA
.

[qtbgo]

Yes， It is a valid start.

[braindeaf]

I've just used this this week to try and schedule an on-call roster.

182 days, exactly 2 shifts per day, one day, one night. Trying to schedule two consecutive nights and one day on its own, so each employee has exactly 3 shifts (2 nights and 1 day which isn't possible)

https://gist.github.com/braindeaf/3d8503cca59d6e0d7c665479832b2ab3

The only thing I couldn't fathom was to try and spread the shifts out as evenly in time as possible, say with almost 90 days gap between each set of shifts (if the grouping of 2 and 1 was indeed possible). The lowest cost solution is arrived at within 20 mins or so. I'm calling my Python script from Ruby by reading input / output via YAML, I'm not sure how to convert it to Ruby (or indeed C++) from this as Python is not my forte.