The problem I want to solve is the same as this text
For example, I have 3 works and 4 tasks. The costs matrix is shown below.
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 95],
]
I need to assign each worker with one task. But I don’t need to minimiz the total cost. Instead, I want to minimiz their extreme range (means that I want to make their working hours as close as possible ).
For example, if work0->task0 work1->task1 work2->task2, then their range is 5, the smallest. This is what I want to get.
I have tried to ues the MIP solver and CP-SAT solver. But there will always be mistakes.
The code below shows how MIP solver deal this problem.
from ortools.linear_solver import pywraplp
def main():
# Data
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 95],
]
num_workers = len(costs)
num_tasks = len(costs[0])
# Solver
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
# Variables
# 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, "")
# Constraints
# Each worker is assigned to exactly one 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 at most one worker.
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) <= 1)
# Objective
objective_terms = []
for i in range(num_workers):
for j in range(num_tasks):
objective_terms.append(costs[i][j] * x[i, j])
objective_cost = max(objective_terms)-min(objective_terms)
solver.Minimize(objective_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"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(f"Worker {i} assigned to task {j}." + f" Cost: {costs[i][j]}")
else:
print("No solution found.")
if __name__ == "__main__":
main()
Running this, the following is thrown:
Operators "<" and ">" not supported with the linear solver
The key code is this:
objective_cost = max(objective_terms)-min(objective_terms)
solver.Minimize(objective_cost)
I know why it’s wrong. The elements’ data type in the list objective_terms are not int. But I don’t kown to modify it. Alos,I can’t think of any other way to deal this.
Is this a problem type I can use or-tools to solve?
Many thanks for your kind and warm help.
user24923465 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.