如何求解满足单调性、归一化与阈值约束的每日权重-Python教程-PHP中文网

如何求解满足单调性、归一化与阈值约束的每日权重

本文介绍如何使用整数线性规划（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，仅需调整矩阵维度。