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

如何用整数线性规划求解满足单调性、归一化与阈值约束的每日权重

本文介绍如何使用 Python 的 scipy.optimize.milp 求解一组严格递减、和为 7 的每日权重，使其加权平均值恰好对 7 个用户低于指定阈值（如 11），通过整数线性规划建模实现精确约束满足。

本文介绍如何使用 python 的 `scipy.optimize.milp` 求解一组严格递减、和为 7 的每日权重，使其加权平均值恰好对 7 个用户低于指定阈值（如 11），通过整数线性规划建模实现精确约束满足。

在时间序列加权分析中，常需设计一组满足多重逻辑约束的权重：既要体现“越近越重要”的单调衰减特性，又要保证全局归一化（如权重和固定为天数），更关键的是——使加权结果在个体层面满足特定统计条件（例如恰好有 k 个用户的加权均值 ≤ 阈值）。这类问题无法通过简单函数（如指数衰减）直接求解，因其第三条约束具有组合离散性（涉及“恰好 k 个满足”的逻辑），必须借助混合整数线性规划（MILP）建模。

核心建模思路

我们将问题转化为一个 MILP 优化模型，引入两类变量：

连续变量：7 个权重 $ w0, w{-1}, \dots, w_{-6} \in \mathbb{R}^+ $
二元变量：10 个指示变量 $ p_i \in {0,1} $，其中 $ p_i = 1 $ 当且仅当第 $ i $ 个用户的加权日均值 $ \leq 11 $

三条约束分别编码如下：

✅ 单调递减（严格）

要求 $ w0 > w{-1} > \cdots > w_{-6} > 0 $。由于 MILP 无法直接表达严格不等式，我们引入微小下界 $ \varepsilon = 10^{-2} $，构造约束：
$$ wj - w{j+1} \geq \varepsilon,\quad j=0,\dots,5 $$
这确保权重呈阶梯式下降，避免数值退化。

✅ 归一化（和为 7）

线性等式约束：
$$ \sum_{j=0}^{6} w_j = 7 $$

✅ 精确阈值满足（恰好 7 人）

对每个用户 $ i $，定义加权均值：
$$ \mui = \frac{1}{7} \sum{j=0}^{6} wj \cdot x{i,j} $$
其中 $ x_{i,j} $ 是原始数据（df.iloc[i, j]）。
引入大 M 法（$ M = 2 \times \max_i \sumj x{i,j} $）将逻辑蕴含转为线性约束：

若 $ p_i = 1 $，则 $ \mu_i \leq 11 $ → $ \sum_j wj x{i,j} \leq 77 + M(1-p_i) $
若 $ p_i = 0 $，则 $ \mu_i > 11 $（松弛处理，实际由目标函数或互补约束隐含）
最终添加计数约束：$ \sum_i p_i = 7 $

完整可运行代码（精确解）

import numpy as np
import pandas as pd
import scipy.sparse
from scipy.optimize import milp, Bounds, LinearConstraint

# 构造示例数据（与问题一致）
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 = df.rename(columns=lambda x: int(x.split('_')[-1]))
m, n = df.shape  # m=10 users, n=7 days

# 参数设置
threshold = 11.0
n_up_to_threshold = 7  # 恰好7人满足
min_decrease = 1e-2
M = 2 * df.sum(axis=1).max()  # 大M值

# === 变量定义：[w0,...,w6, p0,...,p9] ===
# 目标函数：无优化目标（可行解即可）
c = np.zeros(n + m)

# 变量类型：权重连续，predicates二元
integrality = np.concatenate([np.zeros(n, dtype=int), np.ones(m, dtype=int)])

# 边界：权重 > 0，predicates ∈ {0,1}
lb = np.concatenate([np.full(n, 1e-3), np.zeros(m)])
ub = np.concatenate([np.full(n, np.inf), np.ones(m)])

# === 约束集合 ===
# (1) 权重和 = 7
sum_con = LinearConstraint(
    A=np.hstack([np.ones(n), np.zeros(m)]),
    lb=7, ub=7
)

# (2) 严格单调递减：w_j - w_{j+1} >= min_decrease
A_mono = np.zeros((n-1, n+m))
for j in range(n-1):
    A_mono[j, j] = 1
    A_mono[j, j+1] = -1
mono_con = LinearConstraint(A_mono, lb=min_decrease)

# (3) 阈值逻辑约束（大M法）
# p_i = 1 ⇒ sum_j w_j * df[i,j] <h3>注意事项与实践建议</h3>

可行性保障：并非所有 (threshold, k) 组合都存在可行解。若 milp 返回 success=False，可尝试放宽 min_decrease、调整 threshold 或允许软约束（见进阶部分）。
大 M 值选择：M 需足够大以保证逻辑等价，但过大会损害数值稳定性。推荐设为 2 * max_row_sum（如示例中 M≈280）。
性能优化：对于更大规模（如 >50 用户），建议使用专业求解器（如 gurobi 或 cplex）替代 scipy.milp，并启用预求解与分支策略。
软约束变体：若精确满足不可行，可将阈值设为优化变量，最小化其与目标值（如 11）的绝对偏差（见答案中“Approximate solutions”部分），提升鲁棒性。

该方法将业务规则精准翻译为数学规划语言，兼顾严谨性与实用性，是解决带组合逻辑的权重设计问题的标准范式。