摘要

  • 挑战: 解空间维度过高
  • 提出方法: 基于偏好的模型约简
  • 改进效果: 提高 20% 精度，速度提升 2-4 个数量级

引言

  • 应用场景:
    • 供应链 (Supply Chain)
    • 能源管理 (Energy Management)
    • 物流 (Logistics)
  • 挑战:
    • 可扩展性 (Scalability)
    • 可解释性 (Interpretability)
  • 解决方案: 通过模型约简代替直接预测

相关工作

  • 端到端解的预测 (End-to-End Solution Prediction)
  • 优化过程学习 (Learning to Optimize)
  • MILP 模型简化学习 (Learning to Simplify MILP)
  • 先前论文MLOPT的问题：

方法

概念

  • 原MILP问题：

    min⁡xf(c,x)subject tog(A,x)≤b,xI∈Zd,x−I∈Rn−d\min_{x} f(c, x) \quad \text{subject to} \quad g(A, x) \leq b, \quad x_I \in Z^d, \quad x_{-I} \in R^{n-d}

    其中，c∈Rnc \in \mathbb{R}^n 是目标系数向量，AA 是约束矩阵，bb 是约束向量，θ=⟨A,c,b⟩\theta = \langle A, c, b \rangle 表示 MILP 的所有参数。

  • 简化后的问题：

    min⁡xf(c,x)subject togi(Ai,xI,x−I)≤bi,  ∀i∈T(θ)\min_{x} f(c, x) \quad \text{subject to} \quad g_i(A_i, x_I, x_{-I}) \leq b_i, \; \forall i \in T(\theta)

    其中，T(θ)T(\theta) 表示最优解下的紧约束集合，整数变量 xIx_I 被固定为其最优值 xI∗(θ)x^*_I(\theta)。

  • 策略定义：

    s∗(θ)=(T(θ),xI∗(θ))s^*(\theta) = \left(T(\theta), x^*_I(\theta)\right)

    策略由紧约束集合和最优整数变量值组成。

架构图

framework

框架概览

  • 阶段 1: 策略生成与剪枝 (Strategy Generation and Pruning)
  • 阶段 2: 基于偏好的策略学习 (Preference-based Strategy Learning)

策略生成与剪枝

  • 生成: 随机采样 (Random Sampling)
  • 剪枝: 集合覆盖算法 (SETCOVER Algorithm)

基于偏好的学习

  • 奖励定义: 不可行性 + 次优性 (Infeasibility + Suboptimality)
  • 训练: 基于注意力机制的模型 (Attention-based Model)
  • 损失函数: 偏好损失 + 均方误差损失 (Preference Loss + MSE Loss)

实验

数据集

  • MIPLIB
  • 燃料电池管理 (Fuel Cell Management)
  • 库存管理 (Inventory Management)

评价指标

  • 精度 (Accuracy)
  • 不可行性 (Infeasibility)
  • 次优性 (Suboptimality)

结果

  • 性能: 精度提升 (Accuracy Improvement)
  • 速度: 比 Gurobi 快 3 个数量级 (3 Orders Faster than Gurobi)

结论

  • 贡献: 快速且可解释的 MILP 求解 (Fast & Interpretable MILP Solving)
  • 技术: 基于偏好的学习与集合覆盖 (Preference-based Learning, SETCOVER)
  • 未来工作: 扩展到其他优化问题 (Expand to Other Optimization Problems)

思考

  • 无扩展性: 输入为 MILP 参数 θ\theta，这限制了输入尺寸，遇到更大规模的问题只能重新训练
  • 创新有限: 跟先前论文 MLOPT 对比，改进为将评判指标从分数变为偏序关系
  • 简化模型存疑: 简化模型中固定了整数变量取值，其实就是 LP 砍去不重要约束 + 预测整数变量取值，两个做法的结合