建立一个目标功能，涉及在PYOMO中计数以解决分配问题

Question

我的PYOMO模型正在尝试解决一个任务分配问题，其中需要将4个工人分配给8个任务，因此每个工作人员是2个任务。

目标函数之一model.obj2试图最大程度地减少每个工人使用的材料类型的总和。原因是因为每辆将材料运送到工人的卡车只能携带1种材料，因此有效率提高以最大程度地减少卡车访问的总数。

目前正在使用len（set（...））查找分配给工人的两个任务使用的唯一材料的数量，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

警告中的结果

警告：检测到不断的目标，用占位符代替以防止 求解器故障。

这可能解释了为什么model.obj2在初始代码中似乎并未最小化。客观表达可能已转换为标量值？

我可以得到一些帮助以改写PYOMO的正确方法吗？谢谢你！

复制问题的代码

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)

Answer 1

我认为我可以在这里添加两件事，这可能是您缺少的链接...

首先，正如评论中提到的，您输入模型的内容必须是不依赖于变量当时的值的合法表达式创建，因此 len() 等无效。解决方案：对这些类型的计数事物使用二进制变量，然后将它们通过适当的索引求和。

其次，您正确地索引了第一个变量，但您需要引入第二个变量，即决定向工作人员发送一些材料 matl。请参阅下面的示例，该示例引入了此变量，然后使用 big-M 约束将两个决策链接在一起......具体来说，确保模型向工作人员提供所需的材料以完成所需的任务。

代码：

# 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]