![]()
![]()
研究团队
田方正，刘洪喆，虞文武：东南大学
文章下载
Fangzheng TIAN, Hongzhe LIU & Wenwu YU. A Distributed decomposition algorithm for solving large-scale mixed integer programming problem. Sci China Inf Sci, 2024, 67(12): 222205, doi: 10.1007/s11432-024-4210-2
![]()
混合整数规划问题在解决资源分配和路径规划等实际问题中至关重要。由于其NP难的性质，解决大规模MIP问题具有很大挑战性。本文率先给出了分布式非线性混合整数规划架构体系，解决算力爆炸难题：利用约束分配分解技术，对一类大规模非线性混合整数规划问题进行了解耦。根据分解后的解耦形式，设计了分布式的求解算法，提高了求解该类规划问题的效率。这一研究不仅在理论上具有重要意义，还在实验仿真中展示了优于现有方法的性能。本文首次将约束分配分解方法应用在混合整数非线性规划问题中，解决了现有方法仅限于凸规划或线性整数规划的问题。通过分析分解后子问题的连续性和可微性，发现正方向导数和负方向导数对应特定的最优乘子，进一步给出了方向导数的计算方法。在变量分离的情况下，详细研究了分解后子问题的具体形式，发现了子问题在局部上具有凸性。基于这些分析，提出了两种算法，并验证了其收敛性。通过大量模拟实验，这些算法在精度和速度上优于Gurobi求解器，展示了其在解决大规模问题中的实用性和重要贡献。
本文的主要贡献如下：
1. 率先给出了分布式非线性混合整数规划架构体系，解决算力爆炸难题，证明了分解后问题的连续性和可微性；
2. 在变量分离情况下，证明分解后问题局部凸性，为此类问题提供了全局的视野；
3. 基于所研究的性质，设计了分布式算法，并验证了算法的有效性与高效性。
通过一类混合整数规划问题的实验仿真，来说明所提算法的优越性。考虑如下的混合整数规划问题，
其中a_i,b_i,c_i,d_i,e_i 分别随机从集合{1,4,5},{4,2},{1,0.5},{1,3,2},{-1,-0.5} 集合中选择， σ=-1.5。分解后单个优化函数的形式为![]()
图 1-分解函数图示
可以看到，该函数为两个凸函数组合而成，函数值为两者的最小值，说明了所提出理论的正确性。进一步，对不同规模的优化问题进行了仿真求解，求解结果如下图所示。![]()
图 2-求解结果对比图
实验结果表明，与Gurobi求解器对比，达到相同的求解精度，所提出的算法求解时间更少，反映了算法在求解上的高效性。![]()
![]()
![]()
