On the effectiveness of sequential linear programming for the pooling problem

DOI10.1007/S10479-022-05156-7MaRDI QIDQ6103203zbMATH OpenFDO

Authors Andreas Grothey, K. I. M. McKinnon

Publication date 26 June 2023

Published in Annals of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2002.10899

zbMATH Keywords

global optimizationnonlinear programmingpooling problemsequential linear programming

Mathematics Subject Classification ID

Mixed integer programming (90C11) Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Programming involving graphs or networks (90C35)

Abstract: The aim of this paper is to compare the performance of a local solution technique -- namely Sequential Linear Programming (SLP) employing random starting points -- with state-of-the-art global solvers such as Baron and more sophisticated local solvers such as Sequential Quadratic Programming and Interior Point for the pooling problem. These problems can have many local optima, and we present a small example that illustrates how this can occur. We demonstrate that SLP -- usually deemed obsolete since the arrival of fast reliable QP solvers, Interior Point Methods and sophisticated global solvers -- is still the method of choice for an important class of pooling problem when the criterion is the quality of the solution found within a given acceptable time budget. In addition we introduce a new formulation, the qq-formulation, for the case of fixed demands, that exclusively uses proportional variables. We compare the performance of SLP and the global solver Baron on the qq-formulation and other common formulations. While Baron with the qq-formulation generates weaker bounds than with the other formulations tested, for both SLP and Baron the qq-formulation finds the best solutions within a given time budget. The qq-formulation can be strengthened by pq-like cuts in which case the same bounds as for the pq-formulation are obtained. However the associated time penalty due to the additional constraints results in poorer solution quality within the time budget.

Recommendations

• Pooling problem: alternate formulations and solution methods
• Successive Linear Programming at Exxon
• Analysis of MILP techniques for the pooling problem
• Complexity analysis and algorithm design of pooling problem
• Large-scale standard pooling problems with constrained pools and fixed demands

Cites work

• \(\alpha BB\): A global optimization method for general constrained nonconvex problems
• Advances for the pooling problem: modeling, global optimization, and computational studies (Survey)
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Global minimization by reducing the duality gap
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• Nonlinear programming without a penalty function.
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Resolving degeneracy in quadratic programming
• The computational complexity of the pooling problem
• Trust Region Methods

Cited in

(3)

• Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
• Pooling problem: alternate formulations and solution methods
• Preprocessing Nonlinear Functional Constraints with Applications to the Pooling Problem

This page was built for publication: On the effectiveness of sequential linear programming for the pooling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103203)