首页 | 本学科首页   官方微博 | 高级检索  
     

一个求解池化问题的二阶锥逼近算法
引用本文:任烨权,白延琴,李倩,余长君,张连生. 一个求解池化问题的二阶锥逼近算法[J]. 运筹学学报, 2020, 0(2): 61-72
作者姓名:任烨权  白延琴  李倩  余长君  张连生
作者单位:上海大学理学院数学系;上海工程技术大学理学院
基金项目:国家自然科学基金(No.11771275)。
摘    要:池化问题是工业生产计划中的一个重要问题.通过对原料的合理混合,以混合过程的容量及平衡约束等作为约束条件,要求总体生产成本最低.池化问题的优化模型类似于最小费用流问题.然而,由于该问题的复杂性,池化问题即便在只有一个成分约束的情况下依然是强NP-难问题.基于戴彧虹等提出的优化模型,现对模型进行了一系列的转化.首先将模型等价转化成二次非凸优化模型,其次通过对约束的松弛和内逼近分别给出两个近似的二阶锥规划模型.为了获得模型的全局最优解,采用分支定界的策略,通过求解上下界来逼近原问题的最优解.最后,通过算例开展了数值实验,验证了改进模型和算法的有效性.

关 键 词:池化问题  分支定界法  二阶锥规划

A second-order cone programming algorithm for pooling problem
REN Yequan,BAI Yanqin,LI Qian,YU Changjun,ZHANG Liansheng. A second-order cone programming algorithm for pooling problem[J]. OR Transactions, 2020, 0(2): 61-72
Authors:REN Yequan  BAI Yanqin  LI Qian  YU Changjun  ZHANG Liansheng
Affiliation:(Department of Mathematics,College of Sciences,Shanghai University,Shanghai 200444,China;College of Sciences,Shanghai University of Engineering Science,Shanghai 200335,China)
Abstract: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.
Keywords:pooling problem  branch-and-bound  second-order cone program
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号