将代理分配给具有固定开始时间和结束时间的任务的 CP/MILP 问题名称是什么？
What is the CP/MILP problem name for the assignment of agents to tasks with fixed start time and end time?
我正在尝试解决将代理分配给任务的约束满足优化问题。然而，与基本的分配问题不同的是，如果任务不重叠，则可以将代理分配给许多任务。
每个任务都有一个固定的 start_time 和 end_time。
根据一些一元和二元约束将代理分配给任务。
变量 = 任务集
域 = 一组兼容代理（对于每个变量）
约束 = 一元&二元
优化 fct = 一些线性函数
问题示例：为已知到达和离开时间的卡车分配停车位 space（或团队）。
如果文献中有此类问题的准确名称，我很感兴趣。我认为这是某种分配问题。另外，如果你遇到过这个问题，你是如何解决的？
谢谢。
我不知道您描述的特定变体的名称 - 也许其他人知道。但是，这似乎确实适合 CP/MIP 求解器；我会选择 OR-Tools CP-SAT 求解器，它免费、灵活且通常运行良好。
这是一个 Python 的参考实施，假设每辆车都需要分配一个没有重叠的团队，并且目标是尽量减少使用中的团队数量。
该框架允许直接模拟允许/禁止的分配（查看docs）
from ortools.sat.python import cp_model
model = cp_model.CpModel()
## Data
num_vehicles = 20
max_teams = 10
# Generate some (semi-)interesting data
interval_starts = [i % 9 for i in range(num_vehicles)]
interval_len = [ (num_vehicles - i) % 6 for i in range(num_vehicles)]
interval_ends = [ interval_starts[i] + interval_len[i] for i in range(num_vehicles)]
### variables
# t, v is true iff vehicle v is served by team t
team_assignments = {(t, v): model.NewBoolVar("team_assignments_%i_%i" % (t, v)) for t in range(max_teams) for v in range(num_vehicles)}
#intervals for vehicles. Each interval can be active or non active, according to team_assignments
vehicle_intervals = {(t, v): model.NewOptionalIntervalVar(interval_starts[v], interval_len[v], interval_ends[v], team_assignments[t, v], 'vehicle_intervals_%i_%i' % (t, v))
for t in range(max_teams) for v in range(num_vehicles)}
team_in_use = [model.NewBoolVar('team_in_use_%i' % (t)) for t in range(max_teams)]
## constraints
# non overlap for each team
for t in range(max_teams):
model.AddNoOverlap([vehicle_intervals[t, v] for v in range(num_vehicles)])
# each vehicle must be served by exactly one team
for v in range(num_vehicles):
model.Add(sum(team_assignments[t, v] for t in range(max_teams)) == 1)
# what teams are in use?
for t in range(max_teams):
model.AddMaxEquality(team_in_use[t], [team_assignments[t, v] for v in range(num_vehicles)])
#symmetry breaking - use teams in-order
for t in range(max_teams-1):
model.AddImplication(team_in_use[t].Not(), team_in_use[t+1].Not())
# let's say that the goal is to minimize the number of teams required
model.Minimize(sum(team_in_use))
solver = cp_model.CpSolver()
# optional
# solver.parameters.log_search_progress = True
# solver.parameters.num_search_workers = 8
# solver.parameters.max_time_in_seconds = 5
result_status = solver.Solve(model)
if (result_status == cp_model.INFEASIBLE):
print('No feasible solution under constraints')
elif (result_status == cp_model.OPTIMAL):
print('Optimal result found, required teams=%i' % (solver.ObjectiveValue()))
elif (result_status == cp_model.FEASIBLE):
print('Feasible (non optimal) result found')
else:
print('No feasible solution found under constraints within time')
# Output:
#
# Optimal result found, required teams=7
编辑：
@sascha 提出了一个很好的方法来分析（预先知道的）时间 window 重叠，这将使这个问题可以作为一个分配问题来解决。
因此，虽然上面的公式可能不是最佳的（尽管它可能是，取决于求解器的工作方式），但我尝试用建议的最大集团方法替换无重叠条件- 完整代码如下。
我对中等规模的问题（100 辆和 300 辆汽车）进行了一些实验，从经验来看，在较小的问题（~100 辆）上，这确实有所改善 - 平均大约 15% 的最佳解决方案时间；但我找不到对较大（~300）问题的重大改进。这可能是因为我的公式不是最优的；因为 CP-SAT 求解器（也是一个很好的 IP 求解器）足够聪明；或者因为我错过了什么:)
代码：
（这与上面的代码基本相同，其逻辑支持使用网络方法而不是从@sascha 的回答中复制的无重叠方法）：
from timeit import default_timer as timer
from ortools.sat.python import cp_model
model = cp_model.CpModel()
run_start_time = timer()
## Data
num_vehicles = 300
max_teams = 300
USE_MAX_CLIQUES = True
# Generate some (semi-)interesting data
interval_starts = [i % 9 for i in range(num_vehicles)]
interval_len = [ (num_vehicles - i) % 6 for i in range(num_vehicles)]
interval_ends = [ interval_starts[i] + interval_len[i] for i in range(num_vehicles)]
if (USE_MAX_CLIQUES):
## Max-cliques analysis
# for the max-clique approach
time_windows = [(interval_starts[i], interval_ends[i]) for i in range(num_vehicles)]
def is_overlapping(a, b):
return (b[1] > a[0] and b[0] < a[1])
# raw conflicts
# -------------
binary_conflicts = []
for a, b in itertools.combinations(range(len(time_windows)), 2):
if is_overlapping(time_windows[a], time_windows[b]):
binary_conflicts.append( (a, b) )
# conflict graph
# --------------
G = nx.Graph()
G.add_edges_from(binary_conflicts)
# maximal cliques
# ---------------
max_cliques = nx.chordal_graph_cliques(G)
##
### variables
# t, v is true iff point vehicle v is served by team t
team_assignments = {(t, v): model.NewBoolVar("team_assignments_%i_%i" % (t, v)) for t in range(max_teams) for v in range(num_vehicles)}
#intervals for vehicles. Each interval can be active or non active, according to team_assignments
vehicle_intervals = {(t, v): model.NewOptionalIntervalVar(interval_starts[v], interval_len[v], interval_ends[v], team_assignments[t, v], 'vehicle_intervals_%i_%i' % (t, v))
for t in range(max_teams) for v in range(num_vehicles)}
team_in_use = [model.NewBoolVar('team_in_use_%i' % (t)) for t in range(max_teams)]
## constraints
# non overlap for each team
if (USE_MAX_CLIQUES):
overlap_constraints = [list(l) for l in max_cliques]
for t in range(max_teams):
for l in overlap_constraints:
model.Add(sum(team_assignments[t, v] for v in l) <= 1)
else:
for t in range(max_teams):
model.AddNoOverlap([vehicle_intervals[t, v] for v in range(num_vehicles)])
# each vehicle must be served by exactly one team
for v in range(num_vehicles):
model.Add(sum(team_assignments[t, v] for t in range(max_teams)) == 1)
# what teams are in use?
for t in range(max_teams):
model.AddMaxEquality(team_in_use[t], [team_assignments[t, v] for v in range(num_vehicles)])
#symmetry breaking - use teams in-order
for t in range(max_teams-1):
model.AddImplication(team_in_use[t].Not(), team_in_use[t+1].Not())
# let's say that the goal is to minimize the number of teams required
model.Minimize(sum(team_in_use))
solver = cp_model.CpSolver()
# optional
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 8
solver.parameters.max_time_in_seconds = 120
result_status = solver.Solve(model)
if (result_status == cp_model.INFEASIBLE):
print('No feasible solution under constraints')
elif (result_status == cp_model.OPTIMAL):
print('Optimal result found, required teams=%i' % (solver.ObjectiveValue()))
elif (result_status == cp_model.FEASIBLE):
print('Feasible (non optimal) result found, required teams=%i' % (solver.ObjectiveValue()))
else:
print('No feasible solution found under constraints within time')
print('run time: %.2f sec ' % (timer() - run_start_time))
我会将解释为：有冲突的矩形赋值问题
这可以说 比 多项式可解 赋值更难 （NP-hard 通常）问题。
另一个答案中显示的演示可能有效并且 ortools 的 cp-sat 很棒，但是我没有看到使用基于离散时间的推理的充分理由 这里 就像完成的一样：区间变量、找边和合作。基于调度约束（+ 冲突分析/解释）。这些东西完全是矫枉过正，开销会很明显。 我认为没有必要对 时间 进行推理，而只需要对 时间引发的冲突 进行推理。
编辑： 可以将这两种方法（链接+提议）标记为紧凑公式和扩展公式。只要 可扩展性不是问题，扩展公式通常会显示出更强的松弛和更好的（求解）结果 。对于更大的数据，紧凑的方法可能会再次变得更加可行（这里很难猜测，因为调度传播器并不便宜）。
我的建议是：
- (1) 按照基本的分配问题公式 制定一个 整数规划模型 + 使其成为 矩形 -> a worker 被允许在处理所有任务时处理多个任务（一个总和相等下降）
- (2) Add integrality = mark variables as binary -> 因为问题不再满足total unimodularity
- (3) 添加约束禁止冲突
- (4) 添加约束：剩余内容（例如兼容性）
现在这一切都很简单，但我会提出一个关于 (3) 的非天真的改进：
- 冲突可以解释为稳定集多胞体
- 你的冲突是由先验定义的时间windows及其重叠引起的（正如我所解释的那样；这是整个答案背后的核心假设）
- 这是一个区间图（因为时间-windows）
- 所有区间图都是弦图
- 弦图允许在多时间内枚举所有最大派系（意味着只有多项式多）
- 所有最大团的集（枚举）定义了稳定集多胞形的面
- 我们添加为约束的那些（集合中每个元素的约束）！
- （这里使用的图上的稳定集多胞形也允许非常非常强大的半定松弛，但很难预见在哪些情况下这实际上会有所帮助，因为 SDP 更难处理：warmstart在树搜索中；可扩展性；...)
这将导致多尺寸整数规划问题，在使用良好的 IP 求解器时应该非常非常好（商业广告或如果需要开源：Cbc > GLPK).
关于 (3) 的小演示
import itertools
import networkx as nx
# data: inclusive, exclusive
# --------------------------
time_windows = [
(2, 7),
(0, 10),
(6, 12),
(12, 20),
(8, 12),
(16, 20)
]
# helper
# ------
def is_overlapping(a, b):
return (b[1] > a[0] and b[0] < a[1])
# raw conflicts
# -------------
binary_conflicts = []
for a, b in itertools.combinations(range(len(time_windows)), 2):
if is_overlapping(time_windows[a], time_windows[b]):
binary_conflicts.append( (a, b) )
# conflict graph
# --------------
G = nx.Graph()
G.add_edges_from(binary_conflicts)
# maximal cliques
# ---------------
max_cliques = nx.chordal_graph_cliques(G)
print('naive constraints: raw binary conflicts')
for i in binary_conflicts:
print('sum({}) <= 1'.format(i))
print('improved constraints: clique-constraints')
for i in max_cliques:
print('sum({}) <= 1'.format(list(i)))
输出：
naive constraints: raw binary conflicts
sum((0, 1)) <= 1
sum((0, 2)) <= 1
sum((1, 2)) <= 1
sum((1, 4)) <= 1
sum((2, 4)) <= 1
sum((3, 5)) <= 1
improved constraints: clique-constraints
sum([1, 2, 4]) <= 1
sum([0, 1, 2]) <= 1
sum([3, 5]) <= 1
趣闻：
- 商业整数规划求解器甚至 Cbc 甚至可能会尝试在某种程度上对集团约束进行相同的推理，尽管没有假设弦度是 NP-难题
- ortools 的 cp-sat 求解器也有一个代码路径（同样：一般 NP-hard 案例）
- 应该在表达基于冲突的模型时触发（更难决定对基于一般离散时间的调度模型的这种利用）
注意事项
实施/可扩展性
仍有未解决的问题，例如：
- 对每个 worker 复制 max-clique 约束与以某种方式合并它们
- 更 efficient/clever 查找冲突（排序）
- 它会扩展到数据吗：图表有多大/我们需要多少冲突和约束
但这些事情通常遵循实例统计（又名“不要盲目决定”）。
我正在尝试解决将代理分配给任务的约束满足优化问题。然而，与基本的分配问题不同的是，如果任务不重叠，则可以将代理分配给许多任务。 每个任务都有一个固定的 start_time 和 end_time。 根据一些一元和二元约束将代理分配给任务。
变量 = 任务集
域 = 一组兼容代理（对于每个变量）
约束 = 一元&二元
优化 fct = 一些线性函数
问题示例：为已知到达和离开时间的卡车分配停车位 space（或团队）。
如果文献中有此类问题的准确名称，我很感兴趣。我认为这是某种分配问题。另外，如果你遇到过这个问题，你是如何解决的？
谢谢。
我不知道您描述的特定变体的名称 - 也许其他人知道。但是，这似乎确实适合 CP/MIP 求解器；我会选择 OR-Tools CP-SAT 求解器，它免费、灵活且通常运行良好。
这是一个 Python 的参考实施，假设每辆车都需要分配一个没有重叠的团队，并且目标是尽量减少使用中的团队数量。 该框架允许直接模拟允许/禁止的分配（查看docs）
from ortools.sat.python import cp_model
model = cp_model.CpModel()
## Data
num_vehicles = 20
max_teams = 10
# Generate some (semi-)interesting data
interval_starts = [i % 9 for i in range(num_vehicles)]
interval_len = [ (num_vehicles - i) % 6 for i in range(num_vehicles)]
interval_ends = [ interval_starts[i] + interval_len[i] for i in range(num_vehicles)]
### variables
# t, v is true iff vehicle v is served by team t
team_assignments = {(t, v): model.NewBoolVar("team_assignments_%i_%i" % (t, v)) for t in range(max_teams) for v in range(num_vehicles)}
#intervals for vehicles. Each interval can be active or non active, according to team_assignments
vehicle_intervals = {(t, v): model.NewOptionalIntervalVar(interval_starts[v], interval_len[v], interval_ends[v], team_assignments[t, v], 'vehicle_intervals_%i_%i' % (t, v))
for t in range(max_teams) for v in range(num_vehicles)}
team_in_use = [model.NewBoolVar('team_in_use_%i' % (t)) for t in range(max_teams)]
## constraints
# non overlap for each team
for t in range(max_teams):
model.AddNoOverlap([vehicle_intervals[t, v] for v in range(num_vehicles)])
# each vehicle must be served by exactly one team
for v in range(num_vehicles):
model.Add(sum(team_assignments[t, v] for t in range(max_teams)) == 1)
# what teams are in use?
for t in range(max_teams):
model.AddMaxEquality(team_in_use[t], [team_assignments[t, v] for v in range(num_vehicles)])
#symmetry breaking - use teams in-order
for t in range(max_teams-1):
model.AddImplication(team_in_use[t].Not(), team_in_use[t+1].Not())
# let's say that the goal is to minimize the number of teams required
model.Minimize(sum(team_in_use))
solver = cp_model.CpSolver()
# optional
# solver.parameters.log_search_progress = True
# solver.parameters.num_search_workers = 8
# solver.parameters.max_time_in_seconds = 5
result_status = solver.Solve(model)
if (result_status == cp_model.INFEASIBLE):
print('No feasible solution under constraints')
elif (result_status == cp_model.OPTIMAL):
print('Optimal result found, required teams=%i' % (solver.ObjectiveValue()))
elif (result_status == cp_model.FEASIBLE):
print('Feasible (non optimal) result found')
else:
print('No feasible solution found under constraints within time')
# Output:
#
# Optimal result found, required teams=7
编辑：
@sascha 提出了一个很好的方法来分析（预先知道的）时间 window 重叠，这将使这个问题可以作为一个分配问题来解决。
因此，虽然上面的公式可能不是最佳的（尽管它可能是，取决于求解器的工作方式），但我尝试用建议的最大集团方法替换无重叠条件- 完整代码如下。
我对中等规模的问题（100 辆和 300 辆汽车）进行了一些实验，从经验来看，在较小的问题（~100 辆）上，这确实有所改善 - 平均大约 15% 的最佳解决方案时间；但我找不到对较大（~300）问题的重大改进。这可能是因为我的公式不是最优的；因为 CP-SAT 求解器（也是一个很好的 IP 求解器）足够聪明；或者因为我错过了什么:)
代码：
（这与上面的代码基本相同，其逻辑支持使用网络方法而不是从@sascha 的回答中复制的无重叠方法）：
from timeit import default_timer as timer
from ortools.sat.python import cp_model
model = cp_model.CpModel()
run_start_time = timer()
## Data
num_vehicles = 300
max_teams = 300
USE_MAX_CLIQUES = True
# Generate some (semi-)interesting data
interval_starts = [i % 9 for i in range(num_vehicles)]
interval_len = [ (num_vehicles - i) % 6 for i in range(num_vehicles)]
interval_ends = [ interval_starts[i] + interval_len[i] for i in range(num_vehicles)]
if (USE_MAX_CLIQUES):
## Max-cliques analysis
# for the max-clique approach
time_windows = [(interval_starts[i], interval_ends[i]) for i in range(num_vehicles)]
def is_overlapping(a, b):
return (b[1] > a[0] and b[0] < a[1])
# raw conflicts
# -------------
binary_conflicts = []
for a, b in itertools.combinations(range(len(time_windows)), 2):
if is_overlapping(time_windows[a], time_windows[b]):
binary_conflicts.append( (a, b) )
# conflict graph
# --------------
G = nx.Graph()
G.add_edges_from(binary_conflicts)
# maximal cliques
# ---------------
max_cliques = nx.chordal_graph_cliques(G)
##
### variables
# t, v is true iff point vehicle v is served by team t
team_assignments = {(t, v): model.NewBoolVar("team_assignments_%i_%i" % (t, v)) for t in range(max_teams) for v in range(num_vehicles)}
#intervals for vehicles. Each interval can be active or non active, according to team_assignments
vehicle_intervals = {(t, v): model.NewOptionalIntervalVar(interval_starts[v], interval_len[v], interval_ends[v], team_assignments[t, v], 'vehicle_intervals_%i_%i' % (t, v))
for t in range(max_teams) for v in range(num_vehicles)}
team_in_use = [model.NewBoolVar('team_in_use_%i' % (t)) for t in range(max_teams)]
## constraints
# non overlap for each team
if (USE_MAX_CLIQUES):
overlap_constraints = [list(l) for l in max_cliques]
for t in range(max_teams):
for l in overlap_constraints:
model.Add(sum(team_assignments[t, v] for v in l) <= 1)
else:
for t in range(max_teams):
model.AddNoOverlap([vehicle_intervals[t, v] for v in range(num_vehicles)])
# each vehicle must be served by exactly one team
for v in range(num_vehicles):
model.Add(sum(team_assignments[t, v] for t in range(max_teams)) == 1)
# what teams are in use?
for t in range(max_teams):
model.AddMaxEquality(team_in_use[t], [team_assignments[t, v] for v in range(num_vehicles)])
#symmetry breaking - use teams in-order
for t in range(max_teams-1):
model.AddImplication(team_in_use[t].Not(), team_in_use[t+1].Not())
# let's say that the goal is to minimize the number of teams required
model.Minimize(sum(team_in_use))
solver = cp_model.CpSolver()
# optional
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 8
solver.parameters.max_time_in_seconds = 120
result_status = solver.Solve(model)
if (result_status == cp_model.INFEASIBLE):
print('No feasible solution under constraints')
elif (result_status == cp_model.OPTIMAL):
print('Optimal result found, required teams=%i' % (solver.ObjectiveValue()))
elif (result_status == cp_model.FEASIBLE):
print('Feasible (non optimal) result found, required teams=%i' % (solver.ObjectiveValue()))
else:
print('No feasible solution found under constraints within time')
print('run time: %.2f sec ' % (timer() - run_start_time))
我会将解释为：有冲突的矩形赋值问题 这可以说 比 多项式可解 赋值更难 （NP-hard 通常）问题。
另一个答案中显示的演示可能有效并且 ortools 的 cp-sat 很棒，但是我没有看到使用基于离散时间的推理的充分理由 这里 就像完成的一样：区间变量、找边和合作。基于调度约束（+ 冲突分析/解释）。这些东西完全是矫枉过正，开销会很明显。 我认为没有必要对 时间 进行推理，而只需要对 时间引发的冲突 进行推理。
编辑： 可以将这两种方法（链接+提议）标记为紧凑公式和扩展公式。只要 可扩展性不是问题，扩展公式通常会显示出更强的松弛和更好的（求解）结果 。对于更大的数据，紧凑的方法可能会再次变得更加可行（这里很难猜测，因为调度传播器并不便宜）。
我的建议是：
- (1) 按照基本的分配问题公式 制定一个 整数规划模型 + 使其成为 矩形 -> a worker 被允许在处理所有任务时处理多个任务（一个总和相等下降）
- (2) Add integrality = mark variables as binary -> 因为问题不再满足total unimodularity
- (3) 添加约束禁止冲突
- (4) 添加约束：剩余内容（例如兼容性）
现在这一切都很简单，但我会提出一个关于 (3) 的非天真的改进：
- 冲突可以解释为稳定集多胞体
- 你的冲突是由先验定义的时间windows及其重叠引起的（正如我所解释的那样；这是整个答案背后的核心假设）
- 这是一个区间图（因为时间-windows）
- 所有区间图都是弦图
- 弦图允许在多时间内枚举所有最大派系（意味着只有多项式多）
- 所有最大团的集（枚举）定义了稳定集多胞形的面
- 我们添加为约束的那些（集合中每个元素的约束）！
- （这里使用的图上的稳定集多胞形也允许非常非常强大的半定松弛，但很难预见在哪些情况下这实际上会有所帮助，因为 SDP 更难处理：warmstart在树搜索中；可扩展性；...)
这将导致多尺寸整数规划问题，在使用良好的 IP 求解器时应该非常非常好（商业广告或如果需要开源：Cbc > GLPK).
关于 (3) 的小演示
import itertools
import networkx as nx
# data: inclusive, exclusive
# --------------------------
time_windows = [
(2, 7),
(0, 10),
(6, 12),
(12, 20),
(8, 12),
(16, 20)
]
# helper
# ------
def is_overlapping(a, b):
return (b[1] > a[0] and b[0] < a[1])
# raw conflicts
# -------------
binary_conflicts = []
for a, b in itertools.combinations(range(len(time_windows)), 2):
if is_overlapping(time_windows[a], time_windows[b]):
binary_conflicts.append( (a, b) )
# conflict graph
# --------------
G = nx.Graph()
G.add_edges_from(binary_conflicts)
# maximal cliques
# ---------------
max_cliques = nx.chordal_graph_cliques(G)
print('naive constraints: raw binary conflicts')
for i in binary_conflicts:
print('sum({}) <= 1'.format(i))
print('improved constraints: clique-constraints')
for i in max_cliques:
print('sum({}) <= 1'.format(list(i)))
输出：
naive constraints: raw binary conflicts
sum((0, 1)) <= 1
sum((0, 2)) <= 1
sum((1, 2)) <= 1
sum((1, 4)) <= 1
sum((2, 4)) <= 1
sum((3, 5)) <= 1
improved constraints: clique-constraints
sum([1, 2, 4]) <= 1
sum([0, 1, 2]) <= 1
sum([3, 5]) <= 1
趣闻：
- 商业整数规划求解器甚至 Cbc 甚至可能会尝试在某种程度上对集团约束进行相同的推理，尽管没有假设弦度是 NP-难题
- ortools 的 cp-sat 求解器也有一个代码路径（同样：一般 NP-hard 案例）
- 应该在表达基于冲突的模型时触发（更难决定对基于一般离散时间的调度模型的这种利用）
注意事项
实施/可扩展性
仍有未解决的问题，例如：
- 对每个 worker 复制 max-clique 约束与以某种方式合并它们
- 更 efficient/clever 查找冲突（排序）
- 它会扩展到数据吗：图表有多大/我们需要多少冲突和约束
但这些事情通常遵循实例统计（又名“不要盲目决定”）。