融合图神经网络与凸差优化的高效混合整数优化方法

扫码查看

原文链接

万方数据
维普

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

作者：

田鹏超、周乐其、潘比康、石野

展开 >

作者单位：

上海科技大学,上海 201210

上海交通大学,上海 200240

关键词：

深度学习图神经网络凸差算法混合整数线性规划

出版年：

2024

DOI：

10.16453/j.2096-5036.202439

人工智能

ISSN：2096-5036

年,卷(期)：2024.(5)