CODEWITHSUNDEEP
linear-programmingor-tools
abuttars
abuttars

Reputation: 121

Google's OR-Tools - single event planning

Google's OR-Tools provides some example code demonstrating how to solve the nurse-scheduling problem. I'm trying to adapt it to solve an interview-planning scenario wherein a single candidate will attend 2 meetings. Each meeting has the following requirement:

  1. Each meeting must have 2 attendees

Solving Requirement (1) is pretty simple:

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)

This works as expected, printing out a single solution wherein each meeting slot has a (basically) random selection of 2 attendees:

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

But this isn't really what I want. The interview candidate only needs to attend two total meetings (one phone_screen and one in_person) whereas the above "solution" shows 12. I want to end up with something like this:

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

Therefore, we have Requirement (2):

  1. Each meeting type should only occur once

Solving Requirement (2) is trickier for some reason, even though it seems like I should be able to follow a very similar strategy.

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

Adding the above code causes it to fail as an INFEASIBLE solution. Where am I going wrong?

Upvotes: 0

Views: 180

Answers (1)

Stradivari
Stradivari

Reputation: 2766

Shouldn't your first requirement be?

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)

Because it looks like you will have less meetings than slots.

As for your second requirement, I don't quite understand it, do you want each (user, meeting) pair to occur only once?

If so, you can just do:

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)

Upvotes: 1

Related Questions