Towards an unsupervised learning scheme for efficiently solving parameterized mixed-integer programs

Shiyuan Qu

doi:10.1016/j.cor.2025.107290

Towards an unsupervised learning scheme for efficiently solving parameterized mixed-integer programs

2025-09-30

0

PRE

AI

DOI：10.1016/j.cor.2025.107290

原文链接

原文求助

摘要

En 中文

混合整数规划（MIP）已被广泛应用于解决各类现实世界决策问题，但其求解效率仍是一个关键挑战。本文提出了一种新颖的无监督学习方案，用于加速一类MIP问题的求解。与现有的学习优化方法显著不同，我们的方案旨在通过无监督学习方式训练一个自编码器（AE），利用参数化MIP问题族的历史实例最优解数据进行训练。通过精心设计AE架构并利用其统计含义，我们提出了一种简单直接的方法，从离线训练的AE解码器参数构造一类割平面约束。得益于AE的表示能力，这些约束能够可靠地包含新问题实例的最优二进制解。更重要的是，将其整合到未见实例的主MIP问题中，可以得到一个收紧的MIP模型，该模型可在决策时刻使用现成求解器以更高的效率重新求解。我们的方法应用于两个基准问题：一个是批处理过程调度问题，其被表述为混合整数线性规划（MILP）问题；另一个是购物车—杆系统控制问题，其被表述为混合整数二次规划（MIQP）问题。全面的实验结果证明，我们的方法在保持高解质量的同时，显著降低了现成MILP求解器的计算成本。本工作的代码已开源，地址为https://github.com/qushiyuan/AE4BV。

Towards an unsupervised learning scheme for efficiently solving parameterized mixed-integer programs

摘要

期刊

机构

引用论文