谷歌的手术室工具 - 单一活动策划

Question

Google的OR-Tools提供了一些示例代码，演示如何解决护士调度问题。我正在尝试对其进行调整以解决面试计划场景，其中单个候选人将参加 2 次会议。每个会议都有以下要求：

1. 每个会议必须有 2 名与会者

求解需求(1(非常简单：

meetings = ["phone_screen", "in_person"]
users = ["alice", "bob", "carl", "donna"]
days = ["Mon", "Tue", "Wed"]
times = ["morning", "afternoon"]
model = cp_model.CpModel()
# Build a boolean variable for every possible meeting time attendee
data = {}
for meeting in meetings:
for day in days:
for time in times:
for user in users:
id = 'meeting={},day={},time={},user={}'.format(meeting, day, time, user)
data[(meeting, day, time, user)] = model.NewBoolVar(id)
## Requirement 1: Ensure 2 attendees for each time slot
for meeting in meetings:
for day in days:
for time in times:
per_time_data = []
for user in users:
per_time_data.append(data[(meeting, day, time, user)])
model.Add(sum(per_time_data) == 2)
# Solve and print solutions
solver = cp_model.CpSolver()
solver.Solve(model)
for day in days:
for time in times:
for meeting in meetings:
string = '{} {}t| {}t| '.format(day, time, meeting)
for user in users:
if solver.Value(data[(meeting, day, time, user)]) == 1:
string += user + 't'
print(string)

这按预期工作，打印出一个解决方案，其中每个会议时段(基本上(随机选择 2 名与会者：

Mon morning     | phone_screen  | bob   carl    
Mon morning     | in_person     | alice bob     
Mon afternoon   | phone_screen  | alice bob     
Mon afternoon   | in_person     | alice bob     
Tue morning     | phone_screen  | alice bob     
Tue morning     | in_person     | alice bob     
Tue afternoon   | phone_screen  | alice bob     
Tue afternoon   | in_person     | alice bob     
Wed morning     | phone_screen  | alice bob     
Wed morning     | in_person     | alice bob     
Wed afternoon   | phone_screen  | alice bob     
Wed afternoon   | in_person     | alice bob 

但这不是我真正想要的。面试候选人只需要参加两次会议(一次phone_screen和一次in_person(，而上述"解决方案"显示 12 次。我想以这样的东西结束：

Mon morning     | phone_screen  | bob   carl      
Mon afternoon   | in_person     | alice bob

因此，我们有要求(2(：

2. 每种会议类型只能出现一次

由于某种原因，解决需求(2(更棘手，尽管看起来我应该能够遵循非常相似的策略。

## Requirement 2: Ensure only 1 of each type of meeting exists
for meeting in meetings:
per_meeting_data = []
for user in users:
for day in days:
for time in times:
per_meeting_data.append(data[(meeting, day, time, user)])
# Ensure the number of attendees for this meeting type on all days is 2
model.Add(sum(per_meeting_data) == 2)

添加上述代码会导致它作为INFEASIBLE解决方案失败。我哪里出错了？

Answer 1

你的第一个要求不应该是吗？

for meeting in meetings:
for day in days:
for time in times:
per_time_data = []
for user in users:
per_time_data.append(data[(meeting, day, time, user)])
# notice the indentation and <=
model.Add(sum(per_time_data) <= 2)

因为看起来您的会议将少于插槽。

至于你的第二个要求，我不太明白，你希望每个(用户、会议(对只出现一次吗？

如果是这样，您可以执行以下操作：

for meeting in meetings:
for user in users:
per_meeting_data = []
for day in days:
for time in times:
per_meeting_data.append(data[(meeting, day, time, user)])
model.Add(sum(per_meeting_data) == 1)