上海科技大学知识管理系统

混合整数线性规划（MILP）是一种常见的离散组合优化问题,由于决策变量定义域不连续,面对大规模算例时,大多数求解器求解时间很长。l因此,在有限时间内快速获得MILP问题近似解成为重要的发展方向。本研究提出了Neura-DC,一种融合图神经网络与凸差优化的高效混合整数优化求解框架。凸差优化算法可以将原来复杂的MILP问题转化为一系列路径跟踪的线性规划问题,极大降低计算量,但是依赖于较好的初始点;而图神经网络通过二部图编码与特征提取,可以为凸差优化算法预测整数变量初始点进行热l启动,这实现了神经网络与凸差优化算法的协同作用。在三个经典MILP测试问题下,Neura-DC均展示了很高的可行率与较小的对偶间隙,在求解效率上相比主流的求解器和分支定界类学习算法具有显著优势。