构建一个 objective 函数，涉及在 pyomo 中计数以解决分配问题
Building an objective function involving counting in pyomo for assignment problem
我的 Pyomo 模型试图解决一个任务分配问题，其中需要将 4 个工人分配给 8 个任务，因此每个工人分配 2 个任务。
objective 函数之一 model.obj2 试图最小化每个 worker worker 使用的 material 类型的总和。原因是因为每辆运送 materials 给工人的卡车只能运送一种类型的 material，因此可以提高效率以尽量减少卡车的总访问次数。
目前正在使用 len(set(...)) 查找分配给一个工作人员的两个任务使用的唯一 material 的数量，并 sum() 将所有 4 个任务的这个数量相加工人。
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
但是，删除model.obj1（用于调试目的），例如
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
导致警告
WARNING: Constant objective detected, replacing with a placeholder to prevent
solver failure.
这或许可以解释为什么 model.obj2 在初始代码中似乎没有被最小化。 objective 表达式可能已转换为标量值？
我能得到一些帮助以正确的方式为 Pyomo 重写这个 objective 函数吗？谢谢！
重现问题的代码
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)
我想我可以在这里添加 2 件事，它们可能是您遗漏的 links...
首先，如评论中所述，您输入模型的内容必须是不依赖于创建时变量值的合法表达式，因此 len() 等无效。解决方案：对那些类型的计数事物使用二进制变量，然后通过适当的索引对它们求和。
其次，您正确地为第一个变量建立了索引，但是您需要引入第二个变量，即决定派遣工人 w 一些 material matl。请参阅下面的示例，该示例介绍了此变量，然后使用 big-M 约束将两个决策一起 link...。具体而言，确保模型向工作人员提供所需的 material需要它的任务。
代码：
# 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]
我的 Pyomo 模型试图解决一个任务分配问题，其中需要将 4 个工人分配给 8 个任务，因此每个工人分配 2 个任务。
objective 函数之一 model.obj2 试图最小化每个 worker worker 使用的 material 类型的总和。原因是因为每辆运送 materials 给工人的卡车只能运送一种类型的 material，因此可以提高效率以尽量减少卡车的总访问次数。
目前正在使用 len(set(...)) 查找分配给一个工作人员的两个任务使用的唯一 material 的数量，并 sum() 将所有 4 个任务的这个数量相加工人。
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
但是，删除model.obj1（用于调试目的），例如
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
导致警告
WARNING: Constant objective detected, replacing with a placeholder to prevent solver failure.
这或许可以解释为什么 model.obj2 在初始代码中似乎没有被最小化。 objective 表达式可能已转换为标量值？
我能得到一些帮助以正确的方式为 Pyomo 重写这个 objective 函数吗？谢谢！
重现问题的代码
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)
我想我可以在这里添加 2 件事，它们可能是您遗漏的 links...
首先，如评论中所述，您输入模型的内容必须是不依赖于创建时变量值的合法表达式，因此 len() 等无效。解决方案：对那些类型的计数事物使用二进制变量，然后通过适当的索引对它们求和。
其次，您正确地为第一个变量建立了索引，但是您需要引入第二个变量，即决定派遣工人 w 一些 material matl。请参阅下面的示例，该示例介绍了此变量，然后使用 big-M 约束将两个决策一起 link...。具体而言，确保模型向工作人员提供所需的 material需要它的任务。
代码：
# 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]