线性乘积和规划问题的基于D.C.松弛的分支定界算法

作者：张博; 王红雨; 高岳林^*

来源：运筹学学报, 2023, 1-17.

• 全局优化
• 线性乘积和规划
• 分支定界
• D.C.规划松弛技术

线性乘积和规划已出现在工程实践和管理科学等领域,是一类NP-Hard问题。本文针对该问题目标函数的特殊结构,将其重构为一个D.C.(Difference of Convex functions)规划问题。再利用凹函数的凸包络,构造出了一种D.C.松弛问题,并将其分解为两个凸子问题。然后将该D.C.松弛与超矩形的标准二分法相结合,设计了新的分支定界算法,并分析了其理论收敛性和计算复杂度。最后,借助大量数值实验验证了该算法的有效性。

• 单位
  宁夏大学; 北方民族大学