用OR-tools求解多人分配问题

Question

我正在尝试使用Python中的OR工具(OR工具的新手)来解决一个类似于https://developers.google.com/optimization/assignment/assignment_groups的赋值问题。也就是说，我希望将会议分配到4个时隙，供3名与会者参加。我知道与会者%1应该参加M1、M2、M3，与会者%2应该参加M2、M3、M5，与会者%3应该参加M3、M4、M5。其他约束是没有时隙有超过一个会议(对于每个与会者)，并且每个会议被分配到恰好一个时隙(对于每个与会者)。为了简单起见，我假设每个与会者都有4个空闲的时间段。

!pip install ortools
from ortools.sat.python import cp_model # CP-SAT solver (primary constraint solver of ORtools)
from ortools.linear_solver import pywraplp
from __future__ import print_function
from ortools.sat.python import cp_model

model = cp_model.CpModel()
num_meetings = 5
num_slots = 4



#attendees X meetings
my_array = [[1,1,0,0,1],[0,1,1,0,1],[0,0,1,1,1]]

#meetings X attendees
my_array_2 = [[0], [0,1], [1,2], [2], [0,1,2]]

# Declare the variables.
a = []
for i in range(3):
  b = []
  for j in range(num_meetings):
    c = []
    for k in range(num_slots):
      c.append(model.NewIntVar(0, 1, "a[%i,%i,%i]" % (i, j, k)))
    b.append(c)
  a.append(b)
a_array = [a[i][j][k] for i in range(3) for j in range(num_meetings) for k in range(num_slots)]


#Define the attendees of each meeting:
for d in range(3):
    for s in range(num_meetings):
        model.Add(sum(a[d][s][k] for k in range(num_slots)) == my_array[d][s])

#Requirement 1: no timeslot has more than one meeting mapped to it,
for d in range(3):
    for k in range(num_slots):
        model.Add(sum(a[d][s][k] for s in range(num_meetings)) <= 1)

#Requirement 2:
#this should force the attendees with the same meetings to have the same time slot
for i in range(num_meetings):
  print('meeting',i+1)
  print('------------')
  for j in range(len(my_array_2[i])):
    print('attendee',my_array_2[i][j]+1)
    model.Add(sum(a[my_array_2[i][j]][i][k] for k in range(num_slots)) == 1)
  print('------------')



#call the solver:
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
  print('Solved')
else:
  print(status)


#print the solutions
for i in range(3):
  for j in range(num_meetings):
    for k in range(num_slots):
      if solver.Value(a[i][j][k]) == 1:
        print('user',i+1,'meeting',j+1,'slot',k+1, 'value:',solver.Value(a[i][j][k]))

求解器工作到某个点，因为它正确地分配了每个会议，没有与会者在同一时间段中有多个会议。但是，由于某些原因，该解决方案强制前3个时隙中的所有会议，导致最后一个时隙对每个与会者都是空闲的。这会导致与会者参加相同的会议，但每个人都在不同的时间段。理想情况下，需求2将迫使同一会议的与会者在相同的时间段开会。

Answer 1

1. 如果问题因为容量而不可行，则没有额外的约束使其可行
2. 您正在向同一变量列表添加3个不兼容的AddAllowedAssignment()约束。