New multi-commodity flow formulations for the pooling problem

• Published in: Journal of global optimization 2016-12, Vol.66 (4), p.669-710
• Main Authors: Boland, Natashia, Kalinowski, Thomas, Rigterink, Fabian
• Format: Article
• Language: English
• Subjects: Algorithms; Commodities; Computation; Computer Science; Decomposition; Formulations; Linear programming; Mathematics; Mathematics and Statistics; Nonlinear programming; Nonlinearity; Operations Research/Decision Theory; Optimization; Performance evaluation; Raw materials; Real Functions; Solvers; Studies; Variables
• ISSN: 0925-5001; 1573-2916
• DOI: 10.1007/s10898-016-0404-x

The pooling problem is a nonconvex nonlinear programming problem with numerous applications. The nonlinearities of the problem arise from bilinear constraints that capture the blending of raw materials. Bilinear constraints are well-studied and significant progress has been made in solving large instances of the pooling problem to global optimality. This is due in no small part to reformulations of the problem. Recently, Alfaki and Haugland proposed a multi-commodity flow formulation of the pooling problem based on input commodities. The authors proved that the new formulation has a stronger linear relaxation than previously known formulations. They also provided computational results which show that the new formulation outperforms previously known formulations when used in a global optimization solver. In this paper, we generalize their ideas and propose new multi-commodity flow formulations based on output, input and output and (input, output)-commodities. We prove the equivalence of formulations, and we study the partial order of formulations with respect to the strength of their LP relaxations. In an extensive computational study, we evaluate the performance of the new formulations. We study the trade-off between disaggregating commodities and therefore increasing the size of formulations versus strengthening the relaxed linear programs and improving the computational performance of the nonlinear programs. We provide computational results which show that output commodities often outperform input commodities, and that disaggregating commodities further only marginally strengthens the linear relaxations. In fact, smaller formulations often show a significantly better performance when used in a global optimization solver.