Assignment problem worker/task with python - ortools

Question

I have a table like this, in which rows represent the tasks (5) and the columns the workers (3).

   |  w1 |  w2 | w3
--------------------
t1 |  90 |  76 | 75
t2 |  35 |  85 | 55
t3 | 125 |  95 | 90
t4 |  45 | 110 | 95
t5 |  60 | 105 | 80

always --> #tasks > #workers

The values are the "affinity" score between a worker and a task

I have to assign a task t* to a worker w* maximizing the sum of the chosen task scores

A worker may have multiple tasks and must have at least one task
A task can only be assigned once

Possibile solution (not the best, a random one):

w1: [t2, t3] 35 + 125 = 160
w2: [t1]              = 76
w3: [t4, t5] 95 + 80  = 175

Furthermore these is also this constraint: each task s* has a size
sizes = [10, 8, 14, 18, 13] # (len(sizes) = number of rows)

and the ideal overall size that a worker should get is
ideal_size_per_worker = [15, 20, 18] # (len(ideal_size_per_worker) = number of columns)

In this case I want to minimize the absolute error given by the sum of the task sizes and the ideal size. Given the previous solution

w1: [t2, t3] 8 + 14  = 22 -> minimize(abs(22 - 15))
w2: [t1]             = 10 -> minimize(abs(10 - 20))
w3: [t4, t5] 18 + 13 = 31 -> minimize(abs(31 - 18))

I'm using ortools.cp_model (is the right solver for this problem?)
I got stuck implementing the second constraint, having problem defining the absolute difference

The code so far:

from ortools.sat.python import cp_model

model = cp_model.CpModel()

data = [
    [90, 76, 75], 
    [35, 85, 55], 
    [125, 95, 90], 
    [45, 110, 95], 
    [60, 105, 80]
]

n_tasks = len(data)
n_workers = len(data[0])

# Variables
x = {}
for task in range(n_tasks):
    for worker in range(n_workers):
        x[task, worker] = model.NewBoolVar(f'x[{task},{worker}]')

# Each task is assigned to exactly one worker.
for task in range(n_tasks):
    model.AddExactlyOne(x[task, worker] for worker in range(n_workers))

# Each worker takes at least 1 task
for worker in range(n_workers):
    model.AddAtLeastOne(x[task, worker] for task in range(n_tasks))


# Objective, maximize the score sums
objective_terms = []
for task in range(n_tasks):
    for worker in range(n_workers):
        objective_terms.append(scores[task][worker] * x[task, worker])
model.Maximize(sum(objective_terms))


# # stuck here... model. ... Minimize absolute error


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

# Print solution.
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'Total score = {solver.ObjectiveValue()}
')
    for task in range(n_tasks):
        for worker in range(n_workers):
            if solver.BooleanValue(x[task, worker]):
                print(f'task {task} assigned to worker {worker}.' +
                      f' Score = {data[task][worker]}')
else:
    print('No solution found.')

Assignment problem worker/task with python - ortools

0 Answers