2025-11-13T22:16:11.184529

Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

Li, Chen, Li et al.
By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.
academic

Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

基本信息

  • 论文ID: 2501.00307
  • 标题: Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction
  • 作者: Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, Wanyuan Wang
  • 分类: cs.LG cs.AI
  • 发表时间: 2024年12月31日 (arXiv预印本)
  • 机构: 东南大学计算机科学与工程学院，华为诺亚方舟实验室
  • 论文链接: https://arxiv.org/abs/2501.00307

摘要

本文通过利用混合整数线性规划(MILP)结构与解之间的相关性，提出了一种基于机器学习的大规模MILP求解方法。与现有的端到端解学习方法不同，本文学习原始MILP的简化等价模型作为中间步骤。该方法提出了一种基于偏好的模型缩减学习方法，考虑所有缩减模型在每个MILP实例上的相对性能作为偏好信息，并引入注意力机制来捕获偏好信息。实验结果显示，相比最先进的模型缩减ML方法，该方法在解精度上提升近20%，相比商业求解器Gurobi实现了2-4个数量级的加速。

研究背景与动机

问题定义

混合整数线性规划(MILP)在供应链物流、服务调度、能源管理、交通规划等关键领域有广泛应用。在实际工业应用中，MILP实例通常涉及数十万个决策变量和约束条件，现有商业求解器基于精确解法，计算成本高昂，无法满足实时需求。

研究动机

  1. 可扩展性问题：现有ML方法直接学习高维解空间映射，存在可扩展性问题
  2. 缺乏解释性：端到端方法无法提供可解释的解或直观理解
  3. 偏好信息利用不足：现有模型缩减方法仅关注最优缩减模型，忽略了所有缩减模型的重要偏好信息

现有方法局限性

  • 端到端解预测：由于解空间高维性导致预测精度低
  • 学习优化：受决策视野限制，效率有限
  • 现有模型缩减方法：将可行缩减模型视为同等理想标签，未充分利用比较信息

核心贡献

  1. 提出基于偏好的模型缩减学习方法：将缩减模型的性能转换为偏好信息，充分利用实例-策略空间中的比较信息
  2. 设计注意力机制架构：捕获实例与偏好缩减模型之间的相关性，提高学习准确性
  3. 引入SETCOVER剪枝技术：控制缩减模型(标签)数量，生成对所有实例可行的最小标签集
  4. 实现显著性能提升：在真实MILP问题上验证，相比现有方法准确性提升20%，相比Gurobi加速2-4个数量级

方法详解

任务定义

给定参数化MILP问题：

min f(c, x)
s.t. g(A, x) ≤ b
     xI ∈ Z^d, x_{-I} ∈ R^{n-d}

其中θ = ⟨A, c, b⟩表示MILP参数。

最优策略定义：s*(θ) = (T(θ), x*_I(θ))，包括紧约束集合T(θ)和最优解处整数变量值。

目标：学习从参数θ到最优策略s*(θ)的映射。

模型架构

1. 策略生成与剪枝阶段

  • 策略生成：使用Good-Turing估计器确定实例数量，直到N₁/N低于阈值
  • 策略剪枝：构建实例-策略二分图G(V_θ, V_s, E)，将剪枝问题转化为SETCOVER问题
  • 贪心算法：迭代选择覆盖最多未覆盖实例节点的策略节点

2. 基于偏好的策略学习

偏好计算：

r(θᵢ, sⱼ) = -log(p(θᵢ, sⱼ) + d(θᵢ, sⱼ))

其中p(θᵢ, sⱼ)为不可行性，d(θᵢ, sⱼ)为次优性。

偏好定义：

(θᵢ, sⱼ) ≻ (θᵢ, sₖ) ⇔ r(θᵢ, sⱼ) > r(θᵢ, sₖ)

注意力机制编码：

A([θᵢ, S^P]) = softmax(QK^T/√d)V

将每个实例-策略对⟨θᵢ, sⱼ⟩视为token，通过多层注意力机制提取特征。

技术创新点

1. 偏好采样优化

利用偏好的传递性，将策略按偏好排序，仅需M_P个有序偏好样本而非(M_P choose 2)个配对比较，将样本复杂度从二次降至线性。

2. 双重损失函数

  • 偏好损失：
L_p(φ) = -1/N ∑∑[μᵢ,ⱼ log(pᵢ,ⱼ) + (1-μᵢ,ⱼ) log(1-pᵢ,ⱼ)]
  • 奖励差异损失：
L_d(φ) = 1/N ∑∑(r̂ᵢ,σ(j) - r̂ᵢ,σ(j+1) - δᵢ,ⱼ)²
  • 总损失：L_total(φ) = λ₁L_p(φ) + λ₂L_d(φ)

3. Top-k策略推理

在线阶段选择Top-k输出策略作为候选，通过求解缩减模型评估并选择不可行性最低的策略。

实验设置

数据集

  1. MIPLIB：6个场景的真实MILP问题，规模和求解难度各异
  2. 燃料电池能源管理问题：通过增加时间步长T调节问题复杂度
  3. 库存管理问题：5个大规模真实工业问题，平均约10万个约束

评价指标

准确性指标：

accuracy = 1/N |{θᵢ | p(θᵢ, ŝⱼ) ≤ ε₁ ∧ d(θᵢ, ŝⱼ) ≤ ε₂}|

其中不可行性和次优性容忍度均设为1×10⁻⁴。

对比方法

  1. Gurobi：先进商业求解器(启用热启动)
  2. Gurobi Heuristic：Gurobi启发式模式(1秒时间限制)
  3. MLOPT：最适用的基于模型缩减的学习方法
  4. Predict and Search：基于解预测的方法

实现细节

  • 优化器：AdamW，学习率0.0001-0.001
  • 学习率衰减：每10轮线性衰减0.9倍，共100轮
  • 批大小：128
  • 协调参数λ₁：0.8-0.9

实验结果

主要结果

MIPLIB数据集

  • 在大多数场景中，本方法在次优性和可行性方面与Gurobi性能相近
  • 相比MLOPT，在可行性方面略有优势，次优性方面显著改善
  • 启发式方法由于时间限制在多个指标上表现较差

燃料电池能源管理

  • 在最复杂问题上准确性提升近39%
  • 策略剪枝效果显著，特别是随问题规模增加
  • Top-k性能：随k增加模型性能提升，在相同k值下优于MLOPT

库存管理问题

  • 在所有实例上保持可行性，准确性稳定在约90%
  • 在最大规模问题P5(超过27万约束)上，相比MLOPT提升约30%

计算时间分析

  • 相比Gurobi实现3个数量级的时间改进
  • 随问题规模增长时间保持相对稳定
  • 相比MLOPT仅有微小差异(相同k值下)
  • Top-k计算可并行化，进一步提升速度

消融实验

偏好学习vs奖励拟合

在燃料电池数据集上，偏好方法相比直接奖励拟合平均准确性提升约9%，在不可行性和次优性指标上表现更优。

排序采样vs传统采样

排序方法相比传统偏好对采样在各种问题规模下平均准确性提升约8%，同时显著降低训练成本。

相关工作

ML-based MILP求解方法分类

  1. 端到端解预测：直接学习MILP实例到解的映射
  2. 学习优化：学习加速传统精确/启发式方法
  3. 学习简化MILP：学习预处理或缩减MILP规模

本文与现有工作关系

  • 相比端到端方法：避免高维解空间学习问题
  • 相比学习优化：不受决策视野限制
  • 相比现有模型缩减：充分利用偏好信息而非仅考虑最优策略

结论与讨论

主要结论

  1. 基于偏好的模型缩减学习显著提升MILP求解性能
  2. SETCOVER剪枝技术有效控制策略数量
  3. 注意力机制成功捕获实例-策略相关性
  4. 在真实工业问题上实现显著加速和准确性提升

局限性

  1. 方法适用于具有重复结构的同质MILP问题
  2. 需要足够的训练数据来学习有效的偏好模型
  3. 策略生成阶段仍需商业求解器获取最优解
  4. 大规模问题中策略空间可能仍然很大

未来方向

  1. 扩展到更广泛的优化问题类型
  2. 减少对训练数据的依赖
  3. 进一步提升策略生成效率
  4. 探索无监督或半监督学习方法

深度评价

优点

  1. 创新性强：首次系统性地将偏好学习引入MILP模型缩减
  2. 理论基础扎实：基于运筹学理论的模型缩减概念
  3. 实验充分：在多个真实数据集上验证，包括工业级问题
  4. 性能显著：相比现有方法实现substantial改进
  5. 可解释性好：缩减模型对应可解释的操作模式

不足

  1. 适用范围限制：主要适用于参数化MILP问题
  2. 训练成本：仍需大量标注数据(最优解)
  3. 理论分析不足：缺乏收敛性和泛化能力的理论保证
  4. 比较基线有限：主要与一种学习方法(MLOPT)比较

影响力

  1. 学术贡献：为ML4CO领域提供新的研究方向
  2. 实用价值：在工业MILP求解中有直接应用潜力
  3. 可复现性：方法描述详细，实验设置清晰
  4. 启发意义：偏好学习思想可扩展到其他优化问题

适用场景

  1. 在线随机规划：需要快速求解相似MILP实例
  2. 供应链优化：参数变化但结构固定的问题
  3. 实时调度：对求解时间要求严格的应用
  4. 大规模工业优化：商业求解器难以处理的问题

参考文献

论文引用了该领域的重要工作，包括：

  • Bengio, Lodi, and Prouvost (2021): ML for combinatorial optimization survey
  • Bertsimas and Stellato (2022): Online mixed-integer optimization
  • Misra, Roald, and Ng (2022): Learning for constrained optimization
  • 以及大量相关的端到端学习和学习优化方法文献

总体评价：这是一篇高质量的研究论文，在ML4CO领域提出了创新的偏好学习方法。虽然存在一些局限性，但其理论贡献和实践价值都很突出，为大规模MILP求解提供了新的有效途径。