How to accelerate assignment problem with ortools.linear_solver

Question

I am new to ortools.linear_solver, and built the follow code which assigns workers to tasks under the follow demands:

1. I wish to find an assignment where the difference between worker with higher cost, and the one with lower cost is minimized.
2. Each worker has one of the follow Ids ("A", "B", "C" , "D") and some constrains available:

• Some tasks can have only workers with specific Id
• Some set of tasks must have workers with the same Id
• Some set of tasks must have workers ids that their sum is limited (where "A" value is 0, "B" value is 1 and so on).

The follow code does the job perfectly, but when the number of workers/tasks is above 40 , the time for it to solve the problem begin to be not practical , and above 50 I stopped the running after 10 minutes.

How can I accelerate it to a realistic time for N up to says 70 ?

• Are there parameters I can set in order to tune the algorithm? For example, I saw there is flag PRESOLVE_ON, but I didn't succeed to find a function in the python api for settig it, I even don't know if it helps.
• Is it possible to give an initial assignment solution which may accelerate the algorithm for reaching the optimal solution?

from ortools.linear_solver import pywraplp
import numpy as np

# number of workers and tasks
N = 40

# cost table for each worker-task pairs
np.random.seed(0)
costs = np.random.rand(N,N)*100

# workers IDs    
workers_id = (np.random.rand(N)*4).astype(np.uint32)
id_2_idsrt_dict = {0: 'A', 1: 'B', 2: 'C', 3: 'D'}        
workers_id_str = [id_2_idsrt_dict[val] for val in workers_id]
print(workers_id_str)
idsrt_2_id_dict = {}
for id, idstr in id_2_idsrt_dict.items():
   idsrt_2_id_dict[idstr] = id
   print(idsrt_2_id_dict)


num_workers = len(costs)
num_tasks = len(costs[0])

max_cost_limit = np.max(costs)
min_cost_limit = np.min(costs)


# Solver
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")   # better for non integer values
   
   
# Variables (updated with algorithm iterations)
# 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, "")    

# Variables (updated with algorithm iterations)
# tasks_ids[j] is a list of integers variables contains each task's assigned worker id.
tasks_ids = []
for j in range(num_tasks):
   tasks_ids.append( solver.Sum([workers_id[i]*x[i, j] for i in range(num_workers)]) )

# Constraint
# Each worker is assigned to exactly one task.
for i in range(num_workers):
   solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) == 1)

# Constraint
# 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)   

# Constraint
# Task 1 can be assigned only with workers that have the id "A"     
solver.Add(tasks_ids[1] == idsrt_2_id_dict["A"])  

# Constraint
# Tasks 2,4,6 must assigned with workers of the same id
solver.Add(tasks_ids[2] == tasks_ids[4]) 
solver.Add(tasks_ids[2] == tasks_ids[6]) 

# Constraint
# Tasks 10,11,12 must assigned with workers of the same id
solver.Add(tasks_ids[10] == tasks_ids[11]) 
solver.Add(tasks_ids[11] == tasks_ids[12]) 

# Constraint
# Tasks 1,2,3 sum of ids <= 4
solver.Add((tasks_ids[1] + tasks_ids[2] + tasks_ids[3]) <= 4) 

# Constraint
# Tasks 4,5,6 sum of ids <= 4
solver.Add((tasks_ids[4] + tasks_ids[5] + tasks_ids[6]) <= 4) 

# Constraint
# Tasks 7,8,9 sum of ids <= 3
solver.Add((tasks_ids[7] + tasks_ids[8] + tasks_ids[9]) <= 3) 


# Objective
# minimize the difference of assignment higher cost worker and lower cost worker
        
# list of workers costs for an assignment
assignment_workers_costs_list = []
for i in range(num_workers):            
   assignment_workers_costs_list.append( sum([costs[i][j] * x[i, j] for j in range(num_tasks)]) )

# Additional variables for max and min costs
max_cost = solver.Var(lb = min_cost_limit, ub  = max_cost_limit, integer =False, name =  'max_cost')        
min_cost = solver.Var(lb = min_cost_limit, ub  = max_cost_limit, integer =False, name =  'min_cost')

# Constraints to update max and min costs
for i in range(num_workers):
   solver.Add(assignment_workers_costs_list[i] <= max_cost)
   solver.Add(assignment_workers_costs_list[i] >= min_cost)


# Minimize the difference between max and min costs
solver.Minimize(max_cost - min_cost)
        
# Solve
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()

# Print solution.
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
   print(f"Differnece= {solver.Objective().Value()}\n")
   for i in range(num_workers):
      for j in range(num_tasks):
         if x[i, j].solution_value() > 0.5:
         print(f"Worker {i} ({workers_id_str[i]})assigned to task {j}." + f" Cost: {costs[i][j]}")
else:
   print("No solution found.")

Answer 1

Since the problem has a pure integer model, you can try using CP-SAT which is a much faster solver. It internally tries to scale the float coefficients if one doesn't manually do it. You can observe the impact of the scaling in the log.

More information on scaling here: sat_parameters.proto