一个求解池化问题的二阶锥逼近算法

作者：任烨权; 白延琴^*; 李倩; 余长君; 张连生

来源：运筹学学报, 2020, 24(02): 61-72.

DOI：10.15960/j.cnki.issn.1007-6093.2020.02.005

• 池化问题
• 分支定界法
• 二阶锥规划

池化问题是工业生产计划中的一个重要问题.通过对原料的合理混合,以混合过程的容量及平衡约束等作为约束条件,要求总体生产成本最低.池化问题的优化模型类似于最小费用流问题.然而,由于该问题的复杂性,池化问题即便在只有一个成分约束的情况下依然是强NP-难问题.基于戴彧虹等提出的优化模型,现对模型进行了一系列的转化.首先将模型等价转化成二次非凸优化模型,其次通过对约束的松弛和内逼近分别给出两个近似的二阶锥规划模型.为了获得模型的全局最优解,采用分支定界的策略,通过求解上下界来逼近原问题的最优解.最后,通过算例开展了数值实验,验证了改进模型和算法的有效性.

• 单位
  上海大学; 上海工程技术大学