如何用Python Gurobi定义线性均匀度实现多事件均匀时间调度

两种可直接用于线性优化的均匀性定义 #

1. 最小化累积偏差绝对值之和（L1范数） #

作为原卡方（L2）目标的线性替代，核心逻辑是让所有时间点的实际调度累积量和理想累积量的偏差总和最小，实现方式：

• 为每组的每个时间点新增两个非负辅助变量pos_diff_k[i]、neg_diff_k[i]，分别代表第k组第i个时间点的正偏差和负偏差
• 添加约束：cumulative_diff_k[i] = pos_diff_k[i] - neg_diff_k[i]
• 该组的均匀性目标项为sum(pos_diff_k) + sum(neg_diff_k)，为纯线性表达式

2. 最小化最大累积偏差（L∞范数） #

适合要求全局偏差上限的场景，核心逻辑是控制所有时间点的偏差最大值尽可能小，实现方式：

• 为每组新增一个非负辅助变量max_diff_k
• 为该组所有时间点添加约束：pos_diff_k[i] <= max_diff_k、neg_diff_k[i] <= max_diff_k
• 该组的均匀性目标项为max_diff_k，为纯线性表达式

多组事件调度配置步骤 #

1. 每组独立约束配置：为每组事件单独配置禁止时间槽约束、总调度数量约束、累积量计算约束、上述均匀性对应的偏差变量和约束
2. 全局冲突约束：对每个时间槽i，添加约束sum(schedule_k[i] for all k) <= 1，保证同一时间只有最多一个事件占用
3. 多目标组合：
   • 若各组有优先级差异，可给每组的均匀性目标项分配权重，加权求和得到整体线性目标
   • 若需分层优化，可直接使用Gurobi原生的多目标线性优化接口，按优先级顺序优化各组的均匀性指标

代码修改示例（单组L1范数适配） #

仅需要修改原代码的目标相关部分即可：

import numpy as np
import gurobipy as gp
from gurobipy import GRB
times = np.arange(100)
m = gp.Model("try_sched")

schedule_1 = m.addMVar(times.size, vtype=GRB.BINARY, name="schedule_1")
mask1 = np.zeros(times.size)
np.random.seed(42)
mask1[np.round(np.random.uniform(low=0,high=99, size=20)).astype(int)] = 1
m.addConstr(schedule_1 @ mask1 == 0)

n_limit_1 = 30
m.addConstr(schedule_1.sum() == n_limit_1)
desired_cumulative_1 = np.round(times/times.max() * n_limit_1)
cumulative_sched_1 = m.addMVar(times.size, vtype=GRB.CONTINUOUS)

# 替换原二次目标相关的偏差定义
pos_diff_1 = m.addMVar(times.size, vtype=GRB.CONTINUOUS, lb=0)
neg_diff_1 = m.addMVar(times.size, vtype=GRB.CONTINUOUS, lb=0)

m.addConstr(cumulative_sched_1[0] == schedule_1[0])
for i in np.arange(1,times.size):
    m.addConstr(cumulative_sched_1[i] == cumulative_sched_1[i-1]+schedule_1[i])
    m.addConstr(cumulative_sched_1[i] - desired_cumulative_1[i] == pos_diff_1[i] - neg_diff_1[i])
   
# 线性目标替代原二次目标
m.setObjective(pos_diff_1.sum() + neg_diff_1.sum(), GRB.MINIMIZE)
m.optimize()

两种线性度量的调度效果和原二次方案差异极小，完全可以满足常规均匀调度需求，同时支持多目标线性优化配置。

内容的提问来源于stack exchange，提问作者I.P. Freeley