My Pyomo model is trying to solve a task assignment problem where 4 workers needs to be assigned to 8 tasks, so that's 2 tasks per worker.
One of the objective function model.obj2 tries to minimize the sum of the types of materials used by each worker worker. The reason is because every truck transporting materials to the worker can only carry 1 type of material, so there is efficiency gains to minimize the total number of truck visits.
This is currently being done using len(set(...)) to find number of unique materials used by both tasks assigned to a worker, and sum() to add up this number for all 4 workers.
def obj_rule(m):
# Minimize the total costs
obj1 = sum(
costs[i][j] * model.x[w, t] for i, w in enumerate(W) for j, t in enumerate(T)
)
# Minimize the number of unique materials used per worker
obj2 = len(
set(
material
for w in W
for t in T
for material in materials_used[t]
if value(model.x[w, t]) == True
)
)
return 5 * obj1 + 2 * obj2
However, removing model.obj1 (for debugging purposes), such as
def obj_rule(m):
# Minimize the number of unique materials used per worker
obj2 = len(
set(
material
for w in W
for t in T
for material in materials_used[t]
if value(model.x[w, t]) == True
)
)
return obj2
results in the warning
WARNING: Constant objective detected, replacing with a placeholder to prevent solver failure.
This might explain why model.obj2 does not seem to be minimized for in the initial code. The objective expression might have been converted into a scalar value?
Can I get some help to rewrite this objective function the proper way for Pyomo? Thank you!
from pyomo.environ import *
import numpy as np
# 4 workers X 8 tasks
costs = np.array(
[
# workerA
[1, 2, 3, 4, 5, 6, 7, 8],
[1, 2, 3, 4, 5, 6, 7, 8],
# workerB
[8, 7, 6, 5, 4, 3, 2, 1],
[8, 7, 6, 5, 4, 3, 2, 1],
# workerC
[1, 3, 5, 7, 9, 11, 13, 15],
[1, 3, 5, 7, 9, 11, 13, 15],
# workerD
[15, 13, 11, 9, 7, 5, 3, 1],
[15, 13, 11, 9, 7, 5, 3, 1],
]
)
# "stone", "wood", "marble", "steel", "concrete"
materials_used = {
"taskA": ["stone", "wood"],
"taskB": ["marble", "wood"],
"taskC": ["marble", "stone"],
"taskD": ["steel", "stone"],
"taskE": ["marble", "steel"],
"taskF": ["marble", "steel"],
"taskG": ["concrete", "marble"],
"taskH": ["concrete", "steel"],
}
W = [
"workerA1",
"workerA2",
"workerB1",
"workerB2",
"workerC1",
"workerC2",
"workerD1",
"workerD2",
]
T = ["taskA", "taskB", "taskC", "taskD", "taskE", "taskF", "taskG", "taskH"]
model = ConcreteModel()
model.x = Var(W, T, within=Binary, initialize=0)
def obj_rule(m):
# Minimize the total costs
# obj1 = sum(
# costs[i][j] * model.x[w, t] for i, w in enumerate(W) for j, t in enumerate(T)
# )
# Minimize the number of unique materials used per worker
obj2 = len(
set(
material
for w in W
for t in T
for material in materials_used[t]
if value(model.x[w, t]) == True
)
)
return obj2
# return 5 * obj1 + 2 * obj2
model.obj = Objective(
rule=obj_rule,
sense=minimize,
)
def all_t_assigned_rule(m, w):
return sum(m.x[w, t] for t in T) == 1
def all_w_assigned_rule(m, t):
return sum(m.x[w, t] for w in W) == 1
model.c1 = Constraint(W, rule=all_t_assigned_rule)
model.c2 = Constraint(T, rule=all_w_assigned_rule)
opt = SolverFactory("glpk")
results = opt.solve(model)
I think there are 2 things I can add here that might be your missing links...
First, as mentioned in comments, the stuff you feed into the model must be legal expressions that do not depend on the value of the variables at time of creation, so len() etc. are invalid. Solution: use binary variables for those types of counting things and then sum them over appropriate indices.
Second, you are indexing your first variable correctly, but you have a second variable you need to introduce, namely, the decision to send worker w some material matl. See my example below that introduces this variable and then uses a big-M constraint to link the two decisions together.... Specifically, ensure the model delivers a required material to a worker for a task in which it is required.
# worker-task-material assignement
# goal: assign workers to tasks, minimze cost of sending them materials
# individually with a weighted OBJ function
import pyomo.environ as pyo
# some data
tasks = list('ABCDEF')
matls = ['stone', 'steel', 'wood', 'concrete']
big_M = max(len(tasks), len(matls)) # an upper bound on the num of matls needed
# this could be expanded to show quantities required...
material_reqts = [
('A', 'stone'),
('A', 'steel'),
('A', 'wood'),
('B', 'stone'),
('B', 'concrete'),
('C', 'concrete'),
('D', 'steel'),
('D', 'concrete'),
('E', 'stone'),
('E', 'wood'),
('F', 'steel'),
('F', 'wood')]
# convert to dictionary for ease of ingestion...
matls_dict = {(task, matl) : 1 for (task, matl) in material_reqts}
workers = ['Homer', 'Marge', 'Flanders']
# a little delivery cost matrix of matl - worker
worker_matl_delivery_costs = [
[1, 2, 4, 5], # Homer
[2, 3, 1, 1], # Marge
[4, 4, 3, 2]] # Flanders
wm_dict = { (w, m) : worker_matl_delivery_costs[i][j]
for i, w in enumerate(workers)
for j, m in enumerate(matls)}
# salary matrix
worker_task_costs = [
[2.2, 3.5, 1.9, 4.0, 3.8, 2.1],
[1.5, 3.0, 2.9, 4.0, 2.5, 1.6],
[1.4, 4.0, 2.3, 4.4, 2.5, 1.8]]
wt_dict = { (w, t) : worker_task_costs[i][j]
for i, w in enumerate(workers)
for j, t in enumerate(tasks)}
# build model components...
m = pyo.ConcreteModel()
# SETS
m.W = pyo.Set(initialize=workers)
m.T = pyo.Set(initialize=tasks)
m.M = pyo.Set(initialize=matls)
# PARAMS
m.delivery_costs = pyo.Param(m.W, m.M, initialize=wm_dict)
m.salary_costs = pyo.Param(m.W, m.T, initialize=wt_dict)
# note: need a default here to "fill in" the non-requirements...
m.matl_reqts = pyo.Param(m.T, m.M, initialize=matls_dict, default=0)
# VARS
m.Assign = pyo.Var(m.W, m.T, domain=pyo.Binary) # assign worker to task decision
m.Deliver = pyo.Var(m.W, m.M, domain=pyo.Binary) # deliver material to worker decision
# build model
# OBJ
# some conveniences here.... we can make model expressions individually
# for clarity and then combine them in the obj.
# pyo.summation() is a nice convenience too! Could also be done w/generator
delivery = pyo.summation(m.delivery_costs, m.Deliver)
salary = pyo.summation(m.salary_costs, m.Assign)
w1, w2 = 0.5, 0.6 # some arbitrary weights...
m.OBJ = pyo.Objective(expr=w1 * delivery + w2 * salary)
# CONSTRAINTS
# each worker must do at least 2 tasks. (note: this is an extension of your reqt.
# in this in conjunction with constraint below will pair all 6 tasks (2 ea. to workers)
# if more tasks are added, they'll be covered, with a min of 2 each
def two_each(m, w):
return sum(m.Assign[w, t] for t in m.T) >= 2
m.C1 = pyo.Constraint(m.W, rule=two_each)
# each task must be done once...prevents tasks from being over-assigned
def task_coverage(m, t):
return sum(m.Assign[w, t] for w in m.W) >= 1
m.C2 = pyo.Constraint(m.T, rule=task_coverage)
# linking constraint.... must deliver materials for task to worker if assigned
# note this is a "for each worker" & "for each material" type of constraint...
def deliver_materials(m, w, matl):
return m.Deliver[w, matl] * big_M >= sum(m.Assign[w, t] * m.matl_reqts[t, matl]
for t in m.T)
m.C3 = pyo.Constraint(m.W, m.M, rule=deliver_materials)
solver = pyo.SolverFactory('glpk')
results = solver.solve(m)
print(results)
print('Assignment Plan:')
for (w, t) in m.Assign.index_set():
if m.Assign[w, t]:
print(f' Assign {w} to task {t}')
print('\nDelivery Plan:')
for w in m.W:
print(f' Deliver to {w}:')
print(' ', end='')
for matl in m.M:
if m.Deliver[w, matl]:
print(matl, end=', ')
print()
print()
Problem:
- Name: unknown
Lower bound: 18.4
Upper bound: 18.4
Number of objectives: 1
Number of constraints: 22
Number of variables: 31
Number of nonzeros: 85
Sense: minimize
Solver:
- Status: ok
Termination condition: optimal
Statistics:
Branch and bound:
Number of bounded subproblems: 53
Number of created subproblems: 53
Error rc: 0
Time: 0.008975028991699219
Solution:
- number of solutions: 0
number of solutions displayed: 0
Assignment Plan:
Assign Homer to task A
Assign Homer to task F
Assign Marge to task B
Assign Marge to task E
Assign Flanders to task C
Assign Flanders to task D
Delivery Plan:
Deliver to Homer:
stone, steel, wood,
Deliver to Marge:
stone, wood, concrete,
Deliver to Flanders:
steel, concrete,
[Finished in 562ms]