Abstract

The distributed recursion (DR) algorithm is an effective method for solving the pooling problem that arises in many applications. It is based on the well-known P-formulation of the pooling problem, which involves the flow and quality variables; and it can be seen as a variant of the successive linear programming (SLP) algorithm, where the linear programming (LP) approximation problem can be transformed from the LP approximation problem derived by using the first-order Taylor series expansion technique. In this talk, we first propose a new nonlinear programming (NLP) formulation for the pooling problem involving only the flow variables, and show that the DR algorithm can be seen as a direct application of the SLP algorithm to the newly proposed formulation. With this new useful theoretical insight, we then develop a new variant of DR algorithm, called penalty DR (PDR) algorithm, based on the proposed formulation. The proposed PDR algorithm is a penalty algorithm where violations of the (linearized) nonlinear constraints are penalized in the objective function of the LP approximation problem with the penalty terms increasing when the constraint violations tend to be large. Compared with the LP approximation problem in the classic DR algorithm, the LP approximation problem in the proposed PDR algorithm can return a solution with a better objective value, which makes it more suitable for finding high-quality solutions for the pooling problem. Numerical experiments on benchmark and randomly constructed instances show that the proposed PDR algorithm is more effective than the classic SLP and DR algorithms in terms of finding a better solution for the pooling problem.

个人简介

戴彧虹，最优化专家，中国科学院院士，中国科学院数学与系统科学研究院副院长、研究员、博士生导师。主要从事非线性优化理论、算法及其应用研究。担任国际运筹学会联合会(IFORS)副主席、中国数学会第十四届副理事长、中国运筹学会会士。曾获国家自然科学二等奖(2006,排名第二)、中国青年科技奖、钟家庆数学奖、冯康科学计算奖、陈省身数学奖(第16届)、萧树铁应用数学奖(第一届)、运筹应用奖、中国科学院优秀导师奖、中国科学院大学领雁银奖等诸多奖项。