最小化 PuLP 中未分配任务的数量
Minimize number of unallocated tasks in PuLP
我是线性规划的新手，正在尝试使用 PuLP 为志愿者分配任务。我在下面生成了一些虚假数据。在这个假数据集中，50 名志愿者（编号为 V1 到 V50）中的每一个都被分配了 100 个任务（编号为 T1 到 T100）的列表。他们被要求指出他们最愿意承担哪 7 项任务，以及他们想要承担多少任务（他们最多允许承担 3 项任务）。每个任务还分配了一个介于 1 到 3 之间的数字，表示该任务的耗时程度。
我想将任务分配给志愿者，确保每个人都能得到任务，并且他们不会得到太多任务/太重的工作量。在我的初始代码中，我还添加了一个约束条件，即所有任务都应分配给至少一名志愿者。然而，对于我的真实数据集（以及这个测试数据集），我不断得到一个不可行的解决方案，因为没有足够的志愿者来完成所有任务。我查看了其他答案，这些答案表明我可以通过增加惩罚来放松约束。 我如何惩罚未分配的任务，或更改我的 objective 语句以最小化未分配任务的数量？ 我当前的 objective 语句只是最大化分配的数量.
### CREATING DATA
# Setting parameters
np.random.seed(42)
num_tasks = 100
num_volunteers = 50
# Creating list of 100 tasks numbered T1 to T100
tasks = [f"T{i}" for i in range(1,num_tasks + 1)]
# Each task is labelled with a number 1 - 3 that indicates estimated time taken to complete
task_load = dict(zip(tasks, [np.random.choice([1,2,3]) for i in range(num_tasks)]))
# Creating list of 50 volunteers numbered V1 to V50
volunteers = [f"V{i}" for i in range(1,num_volunteers+1)]
# Each volunteer is asked to choose 7 tasks to be assigned
volunteer_choices = dict(zip(volunteers, [list(np.random.choice(tasks, size = 7)) for i in range(num_volunteers)]))
# Each volunteer can choose to take between 1 - 3 tasks
volunteer_max_tasks = dict(zip(volunteers, [np.random.choice([1, 2, 3]) for i in range(num_volunteers)]))
### DEFINING MODEL
# Define model
model = LpProblem(name = "resource-allocation", sense = LpMaximize)
# Define decision variables
variables = LpVariable.dicts("Pair", (volunteers, tasks), 0, None, LpBinary)
# Set list of all possible pairs
pairs = [(v, t) for t in tasks for v in volunteers]
# Set objective
model += (lpSum([variables[v][t] for (v, t) in pairs]))
### SETTING CONSTRAINTS
# All volunteers must be assigned at least one task
for v in volunteers:
model += (lpSum([variables[v][t] for t in tasks]) >= 1)
# Volunteers cannot be assigned to more tasks than they are willing to take on
for v in volunteers:
model += (lpSum([variables[v][t] for t in tasks]) <= volunteer_max_tasks[v])
# Volunteers cannot be assigned too high a work load
for v in volunteers:
model += (lpSum([variables[v][t] * task_load[t] for t in tasks]) <= 6)
# Volunteers cannot be assigned a task they didn't choose
for v in volunteers:
for t in tasks:
if not (t in volunteer_choices[v]):
model += (variables[v][t] == 0)
# All tasks must get a volunteer (CAN I LOOSEN THIS?)
for t in tasks:
model += (lpSum([variables[v][t] for v in volunteers]) >= 1)
我必须重申，我对线性规划非常陌生。我不是一个程序员（只是来自一个人手不足的非政府组织，具有一些自学 Python 知识），我开始专门研究 PuLP 来解决像这样的简单任务分配问题。所以我希望在你的回答中，而不是“叙述”解决方案（例如“为 X 创建一个变量，然后将它包含在你的 objective 函数中”），如果可能的话，你可以写出代码？一些看似相关的问题是 and this?但是我无法弄清楚如何使它适应我的问题。
我最初还有最后一个限制，将分配给每个任务的志愿者人数限制为 3，但我删除了它以试图找出一个可行的解决方案。
# Each task cannot be assigned more than 3 volunteers
for t in tasks:
model += (lpSum([variables[v][t] for v in volunteers]) <= 3)
目标澄清：
我们通常希望确保每位报名参加该计划的志愿者都能完成一项任务！就上下文而言，需要分配任务的计划示例可能包括与学校的外展计划，其中每个学生都被分配从事与我们的事业相关的小项目，以便他们可以更多地了解它。 因此，我们不太关心效率（让尽可能少的工人完成尽可能多的任务），而是确保每个学生都能以最大限度地减少未分配数量的方式获得任务任务。 我希望这对上下文更有意义...
试一试...
一些建议。您的代码很接近，但是您不能在没有可行保证的情况下强制为每个任务分配一次....这就是您的问题所在。
我认为您正在寻找的是我放入的额外变量和约束，用于计算“涵盖”的任务，这与成对分开。这允许 objective 最大化“覆盖”任务（与最小化未分配任务相同）。有一个链接约束来支持它。
我还在 obj 函数中添加了一点“糖”来激励制作更多的对，即使它们不需要完成任务。
这在不到 10 秒的时间内解决了 1000 个任务和 500 个志愿者。如果您的数字比那个大得多（不太可能！），可能会有一些增强功能可以在以后进行调整。
此外，numpy 不需要...并且您有很多不必要的括号和列表结构（如果您这样做 sum 或 LpSum，您可以将这些东西放在括号中（生成器），无需进行列表理解。）
代码：
from pulp import *
from random import choice, sample
### CREATING DATA
# Setting parameters
num_tasks = 10
num_volunteers = 7
# Creating list of 100 tasks numbered T1 to T100
tasks = [f"T{i}" for i in range(1,num_tasks + 1)]
# Each task is labelled with a number 1 - 3 that indicates estimated time taken to complete
task_load = dict(zip(tasks, [choice([1,2,3]) for i in range(num_tasks)]))
# Creating list of 50 volunteers numbered V1 to V50
volunteers = [f"V{i}" for i in range(1,num_volunteers+1)]
# Each volunteer is asked to choose 7 tasks to be assigned
volunteer_choices = dict(zip(volunteers, [list(sample(tasks, k=7)) for i in range(num_volunteers)]))
# Each volunteer can choose to take between 1 - 3 tasks
volunteer_max_tasks = dict(zip(volunteers, [choice([1, 2, 3]) for i in range(num_volunteers)]))
### DEFINING MODEL
# Define model
model = LpProblem(name = "resource-allocation", sense = LpMaximize)
# Define decision pair
pair = LpVariable.dicts("Pair", (volunteers, tasks), cat=LpBinary) # no need for upper/lower bound for binary. :)
task_covered = LpVariable.dicts("Covered", tasks, cat=LpBinary)
# Set list of all possible pairs
pairs = [(v, t) for t in tasks for v in volunteers]
# Set objective
model += lpSum(task_covered[t] for t in tasks) + \
0.05 * lpSum(pair[v][t] for v in volunteers for t in tasks) # a little "sugar" to maximize assignments
# model += (lpSum([pair[v][t] for (v, t) in pairs])) # not needed
### SETTING CONSTRAINTS
# NEW: Link the coverage of task to having at least one volunteer paired with it.
# The model wants to "increase" the covered task variable, so we need to clamp it
# down unless there is at least one pair assigned. Make sense?
for t in tasks:
model += task_covered[t] <= lpSum(pair[v][t] for v in volunteers)
# All volunteers must be assigned at least one task <-- superfluous constraint. Model is "trying" to do this
# for v in volunteers:
# model += lpSum(pair[v][t] for t in tasks) >= 1
# Volunteers cannot be assigned to more tasks than they are willing to take on
for v in volunteers:
model += lpSum(pair[v][t] for t in tasks) <= volunteer_max_tasks[v]
# Volunteers cannot be assigned too high a work load
for v in volunteers:
model += lpSum(pair[v][t] * task_load[t] for t in tasks) <= 6
# Volunteers cannot be assigned a task they didn't choose
for v in volunteers:
for t in tasks:
if not (t in volunteer_choices[v]):
model += pair[v][t] == 0
# All tasks must get a volunteer (CAN I LOOSEN THIS?) # This is where your infeasibility problem was
# for t in tasks:
# model += (lpSum([pair[v][t] for v in volunteers]) >= 1)
model.solve()
for v in sorted(volunteers):
for task in sorted(pair[v]):
if pair[v][task].varValue:
print(f'pair: {v} to task {task}')
产量
Result - Optimal solution found
Objective value: 10.85000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
pair: V1 to task T4
pair: V1 to task T5
pair: V1 to task T9
pair: V2 to task T8
pair: V3 to task T10
pair: V3 to task T9
pair: V4 to task T2
pair: V4 to task T4
pair: V4 to task T7
pair: V5 to task T1
pair: V5 to task T3
pair: V5 to task T4
pair: V6 to task T7
pair: V6 to task T8
pair: V7 to task T4
pair: V7 to task T6
pair: V7 to task T7
[Finished in 176ms]
我是线性规划的新手，正在尝试使用 PuLP 为志愿者分配任务。我在下面生成了一些虚假数据。在这个假数据集中，50 名志愿者（编号为 V1 到 V50）中的每一个都被分配了 100 个任务（编号为 T1 到 T100）的列表。他们被要求指出他们最愿意承担哪 7 项任务，以及他们想要承担多少任务（他们最多允许承担 3 项任务）。每个任务还分配了一个介于 1 到 3 之间的数字，表示该任务的耗时程度。
我想将任务分配给志愿者，确保每个人都能得到任务，并且他们不会得到太多任务/太重的工作量。在我的初始代码中，我还添加了一个约束条件，即所有任务都应分配给至少一名志愿者。然而，对于我的真实数据集（以及这个测试数据集），我不断得到一个不可行的解决方案，因为没有足够的志愿者来完成所有任务。我查看了其他答案，这些答案表明我可以通过增加惩罚来放松约束。 我如何惩罚未分配的任务，或更改我的 objective 语句以最小化未分配任务的数量？ 我当前的 objective 语句只是最大化分配的数量.
### CREATING DATA
# Setting parameters
np.random.seed(42)
num_tasks = 100
num_volunteers = 50
# Creating list of 100 tasks numbered T1 to T100
tasks = [f"T{i}" for i in range(1,num_tasks + 1)]
# Each task is labelled with a number 1 - 3 that indicates estimated time taken to complete
task_load = dict(zip(tasks, [np.random.choice([1,2,3]) for i in range(num_tasks)]))
# Creating list of 50 volunteers numbered V1 to V50
volunteers = [f"V{i}" for i in range(1,num_volunteers+1)]
# Each volunteer is asked to choose 7 tasks to be assigned
volunteer_choices = dict(zip(volunteers, [list(np.random.choice(tasks, size = 7)) for i in range(num_volunteers)]))
# Each volunteer can choose to take between 1 - 3 tasks
volunteer_max_tasks = dict(zip(volunteers, [np.random.choice([1, 2, 3]) for i in range(num_volunteers)]))
### DEFINING MODEL
# Define model
model = LpProblem(name = "resource-allocation", sense = LpMaximize)
# Define decision variables
variables = LpVariable.dicts("Pair", (volunteers, tasks), 0, None, LpBinary)
# Set list of all possible pairs
pairs = [(v, t) for t in tasks for v in volunteers]
# Set objective
model += (lpSum([variables[v][t] for (v, t) in pairs]))
### SETTING CONSTRAINTS
# All volunteers must be assigned at least one task
for v in volunteers:
model += (lpSum([variables[v][t] for t in tasks]) >= 1)
# Volunteers cannot be assigned to more tasks than they are willing to take on
for v in volunteers:
model += (lpSum([variables[v][t] for t in tasks]) <= volunteer_max_tasks[v])
# Volunteers cannot be assigned too high a work load
for v in volunteers:
model += (lpSum([variables[v][t] * task_load[t] for t in tasks]) <= 6)
# Volunteers cannot be assigned a task they didn't choose
for v in volunteers:
for t in tasks:
if not (t in volunteer_choices[v]):
model += (variables[v][t] == 0)
# All tasks must get a volunteer (CAN I LOOSEN THIS?)
for t in tasks:
model += (lpSum([variables[v][t] for v in volunteers]) >= 1)
我必须重申，我对线性规划非常陌生。我不是一个程序员（只是来自一个人手不足的非政府组织，具有一些自学 Python 知识），我开始专门研究 PuLP 来解决像这样的简单任务分配问题。所以我希望在你的回答中，而不是“叙述”解决方案（例如“为 X 创建一个变量，然后将它包含在你的 objective 函数中”），如果可能的话，你可以写出代码？一些看似相关的问题是
我最初还有最后一个限制，将分配给每个任务的志愿者人数限制为 3，但我删除了它以试图找出一个可行的解决方案。
# Each task cannot be assigned more than 3 volunteers
for t in tasks:
model += (lpSum([variables[v][t] for v in volunteers]) <= 3)
目标澄清： 我们通常希望确保每位报名参加该计划的志愿者都能完成一项任务！就上下文而言，需要分配任务的计划示例可能包括与学校的外展计划，其中每个学生都被分配从事与我们的事业相关的小项目，以便他们可以更多地了解它。 因此，我们不太关心效率（让尽可能少的工人完成尽可能多的任务），而是确保每个学生都能以最大限度地减少未分配数量的方式获得任务任务。 我希望这对上下文更有意义...
试一试...
一些建议。您的代码很接近，但是您不能在没有可行保证的情况下强制为每个任务分配一次....这就是您的问题所在。
我认为您正在寻找的是我放入的额外变量和约束，用于计算“涵盖”的任务，这与成对分开。这允许 objective 最大化“覆盖”任务（与最小化未分配任务相同）。有一个链接约束来支持它。
我还在 obj 函数中添加了一点“糖”来激励制作更多的对，即使它们不需要完成任务。
这在不到 10 秒的时间内解决了 1000 个任务和 500 个志愿者。如果您的数字比那个大得多（不太可能！），可能会有一些增强功能可以在以后进行调整。
此外，numpy 不需要...并且您有很多不必要的括号和列表结构（如果您这样做 sum 或 LpSum，您可以将这些东西放在括号中（生成器），无需进行列表理解。）
代码：
from pulp import *
from random import choice, sample
### CREATING DATA
# Setting parameters
num_tasks = 10
num_volunteers = 7
# Creating list of 100 tasks numbered T1 to T100
tasks = [f"T{i}" for i in range(1,num_tasks + 1)]
# Each task is labelled with a number 1 - 3 that indicates estimated time taken to complete
task_load = dict(zip(tasks, [choice([1,2,3]) for i in range(num_tasks)]))
# Creating list of 50 volunteers numbered V1 to V50
volunteers = [f"V{i}" for i in range(1,num_volunteers+1)]
# Each volunteer is asked to choose 7 tasks to be assigned
volunteer_choices = dict(zip(volunteers, [list(sample(tasks, k=7)) for i in range(num_volunteers)]))
# Each volunteer can choose to take between 1 - 3 tasks
volunteer_max_tasks = dict(zip(volunteers, [choice([1, 2, 3]) for i in range(num_volunteers)]))
### DEFINING MODEL
# Define model
model = LpProblem(name = "resource-allocation", sense = LpMaximize)
# Define decision pair
pair = LpVariable.dicts("Pair", (volunteers, tasks), cat=LpBinary) # no need for upper/lower bound for binary. :)
task_covered = LpVariable.dicts("Covered", tasks, cat=LpBinary)
# Set list of all possible pairs
pairs = [(v, t) for t in tasks for v in volunteers]
# Set objective
model += lpSum(task_covered[t] for t in tasks) + \
0.05 * lpSum(pair[v][t] for v in volunteers for t in tasks) # a little "sugar" to maximize assignments
# model += (lpSum([pair[v][t] for (v, t) in pairs])) # not needed
### SETTING CONSTRAINTS
# NEW: Link the coverage of task to having at least one volunteer paired with it.
# The model wants to "increase" the covered task variable, so we need to clamp it
# down unless there is at least one pair assigned. Make sense?
for t in tasks:
model += task_covered[t] <= lpSum(pair[v][t] for v in volunteers)
# All volunteers must be assigned at least one task <-- superfluous constraint. Model is "trying" to do this
# for v in volunteers:
# model += lpSum(pair[v][t] for t in tasks) >= 1
# Volunteers cannot be assigned to more tasks than they are willing to take on
for v in volunteers:
model += lpSum(pair[v][t] for t in tasks) <= volunteer_max_tasks[v]
# Volunteers cannot be assigned too high a work load
for v in volunteers:
model += lpSum(pair[v][t] * task_load[t] for t in tasks) <= 6
# Volunteers cannot be assigned a task they didn't choose
for v in volunteers:
for t in tasks:
if not (t in volunteer_choices[v]):
model += pair[v][t] == 0
# All tasks must get a volunteer (CAN I LOOSEN THIS?) # This is where your infeasibility problem was
# for t in tasks:
# model += (lpSum([pair[v][t] for v in volunteers]) >= 1)
model.solve()
for v in sorted(volunteers):
for task in sorted(pair[v]):
if pair[v][task].varValue:
print(f'pair: {v} to task {task}')
产量
Result - Optimal solution found
Objective value: 10.85000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
pair: V1 to task T4
pair: V1 to task T5
pair: V1 to task T9
pair: V2 to task T8
pair: V3 to task T10
pair: V3 to task T9
pair: V4 to task T2
pair: V4 to task T4
pair: V4 to task T7
pair: V5 to task T1
pair: V5 to task T3
pair: V5 to task T4
pair: V6 to task T7
pair: V6 to task T8
pair: V7 to task T4
pair: V7 to task T6
pair: V7 to task T7
[Finished in 176ms]