这是解决调度问题的尝试。目标是按顺序运行多次，以获得体育联盟的每周时间表，定义如下：
- 有48个人，每个人都按技能顺序排列。
- 每个人都被分配到一个团队。团队由 3 个人组成。
- 排名前 12 的人不能与排名后的 12 人比赛。
- 个人只能互相玩一次。
- 个人之间的对抗不能超过两次（越少越好）。
*个人在代码中被标记为“Pods”，但等同于上述个人。
下面是我试图用来解决这个问题的 ortools 代码。我认为最难的部分是确保目标函数是正确的，并且我适当地构建了约束。
最后，我有一个列（个人）和行（团队）的矩阵。有 16 支球队，我已经构建了目标函数，使得奇数行播放下面的偶数行。目标是最小化每个团队中个人排名之和的差异的绝对值：minimize(sumOf(abs(home_i - away_i) for home/away in teams)). 我不确定我是否正确地将这个成对绝对差之和转换为线性约束。
我有几个主要问题：
- 似乎成本总是1176。为什么会这样？对我来说，最佳解决方案似乎是：
SUM(ABS(team1 - team2)) for all teams，并且由于团队的最小值/最大值相对接近，我预计成本会低得多，特别是考虑到我abs(team1 - team2) == 0从蛮力解决方案中获得了很多增量没有人与其他任何人一起玩过/对抗过其他任何人的初始运行。（我的运行解决方案如下所示） - 如果我尝试按顺序运行此程序（以利用所玩的/反对约束），我会在第二次运行时得出一个不可行的解决方案。我创建了一个纯粹的蛮力解决方案，现在是第 5 周，并且满足这些限制没有问题。蛮力解决方案的主要问题是它现在大约运行了 5-6 天并且没有完成。
- 这段代码需要很长时间才能运行！我在它上面放了一个 5 分钟的计数器，因为无论运行 5 分钟还是 6 小时，它似乎都会产生相同的解决方案……而且它产生的解决方案只是在问题停止运行 6 小时后才产生的。我是否错误地指定了某些东西导致它运行这么长时间？
- 从问题的描述中，代码是否看起来像我想要的那样。我知道代码审查可能超出了这个问题/答案格式的范围，但我想我会问，因为可能需要简短的审查来帮助回答我是否正确指定了目标函数。
谢谢！
from ortools.linear_solver import pywraplp
from ortools.sat.python import cp_model
from ultimate.classes import Pod, Team
def main(pods):
# Declare pods
# pods = [Pod(name=ix, rank=ix) for ix in range(1, 49)]
# sorted_pods = sorted(self.pods, key=lambda x: x.rank, reverse=False)
# Data
num_top = 1
num_bot = 1
max_play_with = 1
max_play_against = 2
# TODO: padding for pod count not divisible by 3
num_teams = int(len(pods) / 3)
if len(pods) % 3 != 0:
raise ValueError("Pods not divisible by 3.")
# Model
model = cp_model.CpModel()
# Variables
# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to team j
x = {}
for ii in range(len(pods)):
for jj in range(num_teams):
x[ii, jj] = model.NewIntVar(0, 1, '')
# Constraints
# Each team is composed of three pods
for jj in range(num_teams):
model.Add(sum([x[ii, jj] for ii in range(len(pods))]) == 3)
# Each pod can only be assigned once
for ii in range(len(pods)):
model.Add(sum([x[ii, jj] for jj in range(num_teams)]) == 1)
# Top pods cannot play bottom pods
for ii in range(num_top):
for jj in range(len(pods) - num_bot, len(pods)):
for kk in range(num_teams):
# print(f'Adding constraint: x[{ii}, {kk}], x[{jj}, {kk}]')
# Same team constraint
model.Add(sum([x[ii, kk], x[jj, kk]]) <= 1)
# Opponent constraint (only add when on an even team iteration)
if kk % 2 == 0:
# print(f'Adding constraint: x[{ii}, {kk}, x[{jj}, {kk + 1}]')
model.Add(sum([x[ii, kk], x[jj, kk + 1]]) <= 1)
# print(f'Adding constraint: x[{ii}, {kk + 1}], x[{jj}, {kk}]')
model.Add(sum([x[ii, kk + 1], x[jj, kk]]) <= 1)
# Pods cannot play with someone more than max_play_with
for ii in range(len(pods)):
# print(f'POD: {pod}')
# print(f'Played with: {[key.rank for key in pod.played_with}]')
for teammate in pods[ii].played_with:
# Add the constraint
if ii == 0:
print(f'Pod: {pods[ii].rank}::: With: {teammate.rank}')
for kk in range(num_teams):
limit = max_play_with - pods[ii].played_with[teammate]['count']
# print(f'WITH: x[{ii}, {kk}], x[{teammate.rank - 1, kk}]')
model.Add(sum([x[ii, kk], x[teammate.rank - 1, kk]]) <= limit)
# Pods cannot play against someone more than max_play_against
for ii in range(len(pods)):
# print(f'POD: {pod}')
# print(f'Played against: {[key.rank for key in pod.played_against}]')
for opponent in pods[ii].played_against:
# Add the constraint
if ii == 0:
print(f'Pod: {pods[ii].rank}::: Against: {opponent.rank}')
for kk in range(num_teams):
limit = max_play_against - pods[ii].played_against[opponent]['count']
# print(f'AGAINST: x[{ii}, {kk}], x[{opponent.rank - 1}, {kk}] <= {limit}]')
model.Add(sum([x[ii, kk], x[opponent.rank - 1, kk]]) <= limit)
# Objective
homes = []
aways = []
for jj in range(num_teams):
for ii in range(len(pods)):
if jj % 2 == 0:
homes.append(pods[ii].rank * x[ii, jj])
else:
aways.append(pods[ii].rank * x[ii, jj])
# Pairwise sum of abs differences: need to minimize in obj fn
# x_loss_abs = [model.NewIntVar(0, 1000000, 'x_loss_abs_%i' % i) for i in range(len(homes))]
x_loss_abs = []
for ih in range(len(homes)):
# v = model.NewIntVar(-1000000, 1000000, 'v') # Temporary variable
# model.Add(v == (homes[ih] - aways[ih])
# model.AddAbsEquality(x_loss_abs[ih], v)
# Different attempt:
v1 = model.NewIntVar(0, 1000, 'v1_%i' % ih)
model.Add(homes[ih] - aways[ih] <= v1)
model.Add(aways[ih] - homes[ih] <= v1)
x_loss_abs.append(v1)
# print('***matchups***')
model.Minimize(sum(x_loss_abs))
# Solve
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60 * 5
solver.parameters.num_search_workers = 8
status = solver.Solve(model)
# Print solution
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f'Total cost = {solver.ObjectiveValue()}\n')
pod_teams = {}
for jj in range(num_teams):
for ii in range(len(pods)):
# Test if x[ii, jj] is 1 (with tolerance for floating point arithmetic).
# if x[ii, jj].solution_value() > 0.5:
if solver.BooleanValue(x[ii, jj]):
if jj in pod_teams:
pod_teams[jj].append(pods[ii])
else:
pod_teams[jj] = [pods[ii]]
teams = []
for tt in range(len(pod_teams)):
print(f'Team{tt}: {sum([pod.rank for pod in pod_teams[tt]])} Pods: {[pod.rank for pod in pod_teams[tt]]}')
team = Team(pods=pod_teams[tt])
teams.append(team)
return teams
elif status == cp_model.INFEASIBLE:
print('INFEASIBLE SOLUTION')
return None
else:
print('NO SOLUTION')
print(dir(cp_model))
print(status)
return None
if __name__ == '__main__':
pods = [Pod(name=ix, rank=ix) for ix in range(1, 49)]
main(pods)
class Pod:
is_bottom = False
is_top = False
def __init__(self, name, rank):
self.name = name
self.rank = rank
self.played_with = {}
self.played_against = {}
def play_with(self, pod):
if pod in self.played_with:
self.played_with[pod]['count'] += 1
# self.played_with (things like week, etc. could go here)
else:
self.played_with[pod] = {'count': 1}
def play_against(self, pod):
if pod in self.played_against:
self.played_against[pod]['count'] += 1
else:
self.played_against[pod] = {'count': 1}
def __str__(self):
return str(self.name)
一次运行后的收益：（我不知道为什么......我原以为成本会产生
Sum(abs(team0 - team1) + ... + abs(team14 - team15)) == (37 + 31 + 11 + 3 + 19 + 3 + 9 + 1) == 114：）
Total cost = 1176.0
Team0: 82 Pods: [1, 39, 42]
Team1: 119 Pods: [38, 40, 41]
Team2: 72 Pods: [2, 33, 37]
Team3: 103 Pods: [32, 35, 36]
Team4: 76 Pods: [18, 27, 31]
Team5: 87 Pods: [28, 29, 30]
Team6: 72 Pods: [21, 25, 26]
Team7: 69 Pods: [22, 23, 24]
Team8: 70 Pods: [16, 20, 34]
Team9: 51 Pods: [15, 17, 19]
Team10: 36 Pods: [9, 13, 14]
Team11: 33 Pods: [10, 11, 12]
Team12: 141 Pods: [46, 47, 48]
Team13: 132 Pods: [43, 44, 45]
Team14: 16 Pods: [3, 5, 8]
Team15: 17 Pods: [4, 6, 7]
连续两次运行后的产量（错误），其中第一次运行的输出被缓存并且个人的队友/对手更新：生成一天的第一个时间表......总成本 = 1176.0
Team0: 82 Pods: [1, 39, 42]
Team1: 119 Pods: [38, 40, 41]
Team2: 72 Pods: [2, 33, 37]
Team3: 103 Pods: [32, 35, 36]
Team4: 76 Pods: [18, 27, 31]
Team5: 87 Pods: [28, 29, 30]
Team6: 72 Pods: [21, 25, 26]
Team7: 69 Pods: [22, 23, 24]
Team8: 70 Pods: [16, 20, 34]
Team9: 51 Pods: [15, 17, 19]
Team10: 36 Pods: [9, 13, 14]
Team11: 33 Pods: [10, 11, 12]
Team12: 141 Pods: [46, 47, 48]
Team13: 132 Pods: [43, 44, 45]
Team14: 16 Pods: [3, 5, 8]
Team15: 17 Pods: [4, 6, 7]
****len(teams): 16
1:0:0:::
generating first schedule of day...
Pod: 1::: With: 39
Pod: 1::: With: 42
Pod: 1::: Against: 38
Pod: 1::: Against: 40
Pod: 1::: Against: 41
INFEASIBLE SOLUTION