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

A second-order cone programming algorithm for pooling problem

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

The pooling problem plays an important role in industrial production planning.The optimization model of this problem is similar to the minimum cost problem.However,due to the complexity of the problem,the pooling problem is strong NP-hard even with only one quality.In this paper,based on the optimization model proposed by Dai,we reformulate the model step by step.First,we reformulated the primal model into a quadratic non-convex optimization model equivalently.Then,we relaxed and inner approximate quadratic non-convex optimization model into both second-order cone programming problem,respectively.To solve both second-order cone programming problem,we used the branch and bound method to approximate the optimal solution of the original problem by solving the upper and lower bounds.Finally,we carried out the numerical experiments by using seven examples to demonstrate the effectiveness of our models and the algorithm.