本文介绍如何使用整数线性规划（ilp）在 python 中求解一组严格递减、和为固定值且能使恰好 k 个个体加权均值低于指定阈值的每日权重，适用于时间衰减建模、动态评分等场景。
本文介绍如何使用整数线性规划（ilp）在 python 中求解一组严格递减、和为固定值且能使恰好 k 个个体加权均值低于指定阈值的每日权重，适用于时间衰减建模、动态评分等场景。
在实际数据分析中，我们常需为不同时间点（如最近7天）分配权重，以反映“越近越重要”的业务逻辑。但仅靠指数衰减等启发式方法难以同时满足三项硬性约束：
-
严格单调递减：
w₀ > w₋₁ > w₋₂ > … > w₋₆ > 0； -
归一化约束：所有权重之和等于总天数（即
∑wᵢ = 7）； - 精确阈值控制：加权平均值 ≤ 阈值（如11）的个体数量恰好为7个（而非“至少”或“最多”）。
这类问题本质上是带逻辑约束的优化问题，无法通过解析法或简单数值搜索可靠求解，必须借助混合整数线性规划（MILP）建模。
核心建模思路
我们将问题转化为一个 MILP 模型，引入两类变量：
- 连续变量
w₀…w₋₆表示待求权重； - 二元变量
pᵢ ∈ {0,1}表示第i个个体是否满足weighted_meanᵢ ≤ threshold。
关键约束设计如下：
1. 权重和约束（线性等式）
sum_constraint = LinearConstraint(
A=np.concatenate((np.ones(7), np.zeros(10))), # 7 weights + 10 predicates
lb=7, ub=7
)2. 严格单调性约束（线性不等式）
为避免数值退化，要求相邻权重差 ≥ ε（如 1e-2）：
antimonotonic_constraint = LinearConstraint(
A=scipy.sparse.diags_array(
(np.ones(6), -np.ones(6)), offsets=(0, 1), shape=(6, 17)
),
lb=1e-2
)3. 阈值逻辑约束（大M法）
对每个个体 i，用大M法将逻辑条件 pᵢ = 1 ⇔ (w·xᵢ)/7 ≤ threshold 转为线性约束：
- 若
pᵢ = 1，则w·xᵢ ≤ 7×threshold； - 若
pᵢ = 0，则w·xᵢ > 7×threshold（松弛为w·xᵢ ≥ 7×threshold + ε）。
实际实现中采用标准大M形式：# Lower bound: p_i = 1 ⇒ w·x_i ≤ 7*threshold # Upper bound: p_i = 0 ⇒ w·x_i ≥ 7*threshold + ε (approximated via M) mean_constraint = LinearConstraint( A=scipy.sparse.hstack((df.values / threshold, scipy.sparse.diags_array(np.full(10, 7)))), lb=7, ub=14 )
4. 精确计数约束（线性等式）
强制恰好 k=7 个 pᵢ 为1：
disjunction_constraint = LinearConstraint(
A=np.concatenate((np.zeros(7), np.ones(10))),
lb=7, ub=7
)完整可运行示例（基于 scipy.optimize.milp）
import numpy as np
import pandas as pd
import scipy.sparse
from scipy.optimize import milp, Bounds, LinearConstraint
# 构造示例数据（10人×7天）
np.random.seed(42)
df = pd.DataFrame(np.random.randint(8, 15, size=(10, 7)))
df.columns = ['day_0', 'day_-1', 'day_-2', 'day_-3', 'day_-4', 'day_-5', 'day_-6']
df.index.name = 'id'
# 重命名列为整数索引便于矩阵运算
df.columns = pd.Index([-i for i in range(7)], name='day') # day_0→0, day_-1→-1, ...
m, n = df.shape # m=10 individuals, n=7 days
# 决策变量：[w0,...,w6, p0,...,p9]
# 权重连续，predicates 为二进制
c = np.zeros(n + m) # 无目标函数（可行性问题）
integrality = np.concatenate((np.zeros(n), np.ones(m, dtype=int)))
# 约束1：权重和为7
sum_con = LinearConstraint(
A=np.concatenate((np.ones(n), np.zeros(m))),
lb=7, ub=7
)
# 约束2：严格递减（最小间隔1e-3）
min_gap = 1e-3
A_mono = scipy.sparse.diags_array(
(np.ones(n-1), -np.ones(n-1)), offsets=(0,1), shape=(n-1, n+m)
)
mono_con = LinearConstraint(A_mono, lb=min_gap)
# 约束3：阈值逻辑（大M法，M取足够大值）
threshold = 11.0
M = 2 * df.sum(axis=1).max() # 安全上界
A_thresh = scipy.sparse.hstack((
df.values, # w·x_i terms
scipy.sparse.diags_array(np.full(m, M)), # M·p_i
-np.full((m, 1), 7 * threshold) # -7*threshold
), format='csc')
thresh_con = LinearConstraint(A_thresh, lb=0, ub=M)
# 约束4：恰好7个个体满足条件
count_con = LinearConstraint(
A=np.concatenate((np.zeros(n), np.ones(m))),
lb=7, ub=7
)
# 变量边界
bounds = Bounds(
lb=np.concatenate((np.full(n, 1e-3), np.zeros(m))),
ub=np.concatenate((np.full(n, np.inf), np.ones(m)))
)
# 求解
result = milp(
c=c,
integrality=integrality,
bounds=bounds,
constraints=[sum_con, mono_con, thresh_con, count_con],
method='highs'
)
if not result.success:
raise RuntimeError(f"MILP failed: {result.message}")
weights, preds = result.x[:n], result.x[n:]
means = df @ (weights / 7)
print("✅ 求解成功！")
print(f"权重 w₀..w₋₆ = {weights.round(4)}")
print(f"满足阈值的个体数 = {int(preds.sum())}（预期：7）")
print(f"各ID加权均值:\n{means.round(4)}")注意事项与调优建议
-
数值稳定性：严格单调性需设置合理
min_gap（如1e-3），过小易导致求解器数值失败； -
大M选择：
M应略大于w·xᵢ的理论最大值，过大可能削弱约束紧致性； -
求解器选择：推荐
method='highs'（SciPy 1.9+ 默认），支持大规模稀疏约束； -
无解处理：若
milp返回success=False，可尝试放宽min_gap、调整threshold或检查数据是否物理可行（例如所有个体历史值均 >11，则不可能有7个满足 ≤11）； -
扩展性：该框架天然支持任意天数
n和个体数m，仅需调整矩阵维度。
? 进阶提示：若业务允许阈值柔性浮动，可将
threshold设为连续变量并最小化其与目标值（如12）的绝对偏差，此时需引入额外误差变量与绝对值线性化技巧（见答案中的“Approximate solutions”部分）。
通过本方法，你不再依赖经验衰减公式，而是以数学严谨性直接求解满足多重业务规则的最优权重——这是构建可信、可解释、合规的数据驱动策略的关键一步。
