Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming

会议: ICLR2026
arXiv: 2508.18742
代码: https://github.com/Liwow/Constraint_Matters
领域: 优化/理论
关键词: MILP, constraint reduction, tight constraint, multi-modal representation, GNN

一句话总结

提出基于约束缩减的 MILP 模型简化框架：用信息论启发的启发式规则识别关键紧约束（CTC），设计融合实例级和抽象级信息的多模态 GNN 表征来预测 CTC，在大规模 MILP 上解质量提升 50%+、计算时间减少 17.47%。

研究背景与动机

1. 领域现状：ML-based MILP 求解主要通过变量缩减加速——预测并固定部分变量值。GNN 双部图表征是主流。
2. 现有痛点：(a) 变量缩减预测错误可能导致不可行解；(b) 约束缩减几乎未被研究；(c) 直接固定所有紧约束效果不稳定（最好 200x 加速，最坏反而减速）。
3. 核心矛盾：不同紧约束对求解加速贡献差异巨大，需要选择性固定。
4. 切入角度：信息论——固定约束强度 \(\rho\) 衡量局部可行域缩减比例，信息增益 \(\Delta H = -\log \rho\) 指导选择。
5. 核心idea一句话：用信息增益排序约束类别重要性→只固定高增益关键紧约束 + 多模态 GNN 预测。

方法详解

整体框架

多模态表征（实例双部图 + 抽象类型双部图的层间消息传递）→ CTC 识别（10 种原型约束→信息增益排序→选高增益子集）→ 预测并固定 CTC → 求解器。

关键设计

1. 关键紧约束识别:
2. 固定约束强度 \(\rho(C_i) = |S_{\hat{C}_i}|/|S_{C_i}|\)，信息增益 \(\Delta H = -\log \rho\)

3. Set Packing 强度弱（\(n/(n+1)\)），Knapsack 强度强（\(O(1/A\sqrt{n})\)）→ 优先固定后者

4. 多模态 GNN 表征:

5. 低层：标准实例双部图 GNN（系数矩阵边）
6. 高层：抽象类型图（PLM 编码文本描述为初始特征）
7. 层间：Cross-Attention 融合 + 门控机制传回实例节点

损失函数

二分类交叉熵预测每个约束是否为 CTC。

实验关键数据

主实验

方法	Primal Gap ↓	时间变化	说明
Gurobi 直接	基线	378.2s	商用求解器
最佳约束固定	-	1.85s	Oracle 上界
Ours	↓50%+	↓17.47%	学习选择 CTC

关键发现

• 约束缩减与变量缩减互补，结合效果最好
• 只固定 5% 高质量约束即可显著加速
• 抽象模型（类别语义信息）对跨实例泛化至关重要

亮点与洞察

• 约束缩减视角：ML4Optimization 领域首次系统研究——打开新加速维度
• 信息论指导：原则性的约束重要性度量，非随机启发式
• MILP 的"多模态"定义新颖：抽象模型+实例模型 = 多模态

局限性 / 可改进方向

• 局部解耦假设（约束间独立）不完全成立
• CTC 标注需要 oracle 最优解，标注成本高
• 仅验证二元整数变量

相关工作与启发

• vs 变量缩减：互补方向。本文从对偶视角预测约束状态
• vs Bertsimas & Stellato：预测所有紧约束 vs 只选关键子集
• vs Gasse et al. GNN：加入类别语义 = 更好泛化

评分

• 新颖性: ⭐⭐⭐⭐⭐ 约束缩减+信息论+多模态表征的组合
• 实验充分度: ⭐⭐⭐⭐ 大规模验证充分
• 写作质量: ⭐⭐⭐⭐ 动机清晰
• 价值: ⭐⭐⭐⭐⭐ 为 ML4Optimization 开辟新方向