Minimize variance Nurse scheduling problem takes forever to run with cp_model

[NaamaDayan]

Hi there, I am new to or-tools and I would appriciate your help with the following: I want my algorithm to support fairness. Each day, I have 6 shifts (4 hours each), and each shift has 9 positions (types) that needs to be assigned. For every shift & type I calculate a fairness_score. I calculate for each nurse the total fairness score of her previous and current assignments. My aim is to minimize the variance of this score. The algorithm currently works, however, when I add a few more constraints (described in the for loop which iterate the variable constraints), the algorithm takes forever to run. Also, when I remove the minimization criterion, the algorithm converges and stops. I guess I have a problem in my minimization criterion, but I cannot figure it out. I attach here the relevant code for the problem:

avg_shifts_per_nurse =  1.0 * (num_shifts_per_day * num_days * num_shift_types) / num_nurses
fairness = calc_fairness(history) #calc fairness according to previous scheduling
avg_fairness = sum(list(fairness.values()))/len(list(fairness.values()))

model = cp_model.CpModel()
shifts = {}
for n in all_nurses:
    for d in all_days:
        for s in all_shifts:
            for t in all_types:
                if schedule_is_not_needed(d, s, t):
                    continue
                shifts[(n, d,
                        s, t)] = model.NewBoolVar('shift_n%id%is%it%i' % (n, d, s, t))

# nurse i cannot be assign to shift s on day d (in any type)
for i in soldier_constraints.index:
    for c in constraints:
          d= schedule_hours[c][0]
          s= schedule_hours[c][1]
          model.Add(sum(shifts[(i, d, s, type)] for type in all_types) == 0)

min_shifts_per_nurse = (num_shifts_per_day * num_days * shift_types) // num_nurses
if (num_shifts_per_day * num_days * shift_types) % num_nurses == 0:
    max_shifts_per_nurse = min_shifts_per_nurse
else:
    max_shifts_per_nurse = min_shifts_per_nurse + 1
for n in all_nurses:
    num_shifts_worked = 0
    for d in all_days:
        for s in all_shifts:
            for t in all_types:
                if schedule_is_not_needed(d, s, t):
                    continue
                num_shifts_worked += shifts[(n, d, s, t)]
    model.Add(min_shifts_per_nurse <= num_shifts_worked)
    model.Add(num_shifts_worked <= max_shifts_per_nurse)

for n in all_nurses:
    TOP = 1000
    a = model.NewIntVar(-TOP, TOP, 'a_var')
    model.Add(a == (sum(calc_fairness_for_soldier(s, t, n) * shifts[(n, d, s, t)] for d in all_days for s in all_shifts for t in all_types) - int(round(avg_shifts_per_nurse * avg_fairness))))
    square_a = model.NewIntVar(0, TOP**2, 'square_a')
    model.AddMultiplicationEquality(square_a, [a, a])
    model.Minimize(square_a)

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

#additional functions
def calc_fairness(files):
    dfs = [pd.read_csv('scheduler/history_schedules/'+file+'.csv') for file in files]
    names = soldier_constrains['name'].values
    fairness_score =  dict([(name, 0) for name in names])
    for df in dfs:
        for i, row in df.iterrows():
            for ind in row.index[4:]:
                if row[ind]==row[ind] and row[ind]!=' ' and row[ind] in names:
                    fairness_score[row[ind]] += calc_fairness_for_soldier(row['shift ind'], ind, row[ind], is_history=True)
    for i in fairness_score.keys():
        fairness_score[i] = fairness_score[i] // len(dfs)
    return fairness_score

def calc_fairness_for_soldier(s, t, name):
    fairness_for_name = 0
    if name == name:
        fairness_for_name -= 2
    if 'rachuv' in t and name==name:
        fairness_for_name += 1
    if 'atuda' in t and name==name:
        fairness_for_name += 1
    if s >= 4 and name==name:
        fairness_for_name -= 1
    if 'CC A' in t and name==name:
        fairness_for_name -= 1
    if 'CC B' in t and name==name:
        fairness_for_name += 1
    return fairness_for_name

Thank you very much! Any advice or help will be very appriciated!

[ghost]

Try setting:

solver.parameters.num_search_workers = 8

before solving.

[lperron]

And this is not a solver issue. Please repost on the mailing list or on the discussions.