This is an online assignment problem and yet can be considered as an assignment problem with a sequence. Assume that workers are coming into the system sequentially and I want to assign a task to them based on their cost for each task. I have set up the python model without the sequence constraint, I just couldn't figure out how to mandate the order: This example from the OR-Tools: In the example there are four workers (numbered 0-3) and four tasks (numbered 0-3).
The costs of assigning workers to tasks are shown in the following table.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 90 | 80 | 75 | 70 |
| 1 | 35 | 85 | 55 | 65 |
| 2 | 125 | 95 | 90 | 85 |
| 3 | 45 | 110 | 95 | 115 |
The problem is to assign each worker to at most one task, with no two workers performing the same task while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.
Assume that I want to force an order/ sequence. Say worker 0 has to be assigned first worker 2, then worker 3... So in practice:
- worker 0 assigned to task 3 (lowest cost)
- worker 1 assigned to task 0 (lowest cost)
- worker 2 assigned to task 2 (task 3 has the lowest cost but since it is already assigned to worker 0 it is not available)
- worker 3 assigned to task 1
MIP solution The following sections describe how to solve the problem using the MIP solver as an assignment problem without enforcing the order.
Import the libraries The following code imports the required libraries.
from ortools.linear_solver import pywraplp
The following code declares the MIP solver.
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')
The following code creates the data for the problem.
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 85],
[45, 110, 95, 115],
]
num_workers = len(costs)
num_tasks = len(costs[0])
The following code creates binary integer variables for the problem.
# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for i in range(num_workers):
for j in range(num_tasks):
x[i, j] = solver.IntVar(0, 1, '')
The following code creates the constraints for the problem.
# Each worker is assigned to at most 1 task.
for i in range(num_workers):
solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)
# Each task is assigned to exactly one worker.
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)
HERE I want to add another constraint(s) that forces the order
The following code creates the objective function for the problem.
objective_terms = []
for i in range(num_workers):
for j in range(num_tasks):
objective_terms.append(costs[i][j] * x[i, j])
solver.Minimize(solver.Sum(objective_terms))
The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.
Invoke the solver The following code invokes the solver and prints the solution.
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
print('Total cost = ', solver.Objective().Value(), '\n')
for i in range(num_workers):
for j in range(num_tasks):
# Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
if x[i, j].solution_value() > 0.5:
print('Worker %d assigned to task %d. Cost = %d' %
(i, j, costs[i][j]))
