Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/26780
Title: | New multi-commodity flow formulations for the pooling problem | Contributor(s): | Boland, Natashia (author); Kalinowski, Thomas (author) ; Rigterink, Fabian (author) | Publication Date: | 2016-12 | Early Online Version: | 2016-02-02 | DOI: | 10.1007/s10898-016-0404-x | Handle Link: | https://hdl.handle.net/1959.11/26780 | Abstract: | 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. | Publication Type: | Journal Article | Grant Details: | ARC/LP110200524 | Source of Publication: | Journal of Global Optimization, 66(4), p. 669-710 | Publisher: | Springer New York LLC | Place of Publication: | United States of America | ISSN: | 1573-2916 0925-5001 |
Fields of Research (FoR) 2008: | 010303 Optimisation | Fields of Research (FoR) 2020: | 490304 Optimisation | Socio-Economic Objective (SEO) 2008: | 970101 Expanding Knowledge in the Mathematical Sciences | Socio-Economic Objective (SEO) 2020: | 280118 Expanding knowledge in the mathematical sciences | Peer Reviewed: | Yes | HERDC Category Description: | C1 Refereed Article in a Scholarly Journal |
---|---|
Appears in Collections: | Journal Article School of Science and Technology |
Files in This Item:
File | Size | Format |
---|
SCOPUSTM
Citations
22
checked on Jun 15, 2024
Page view(s)
1,508
checked on Jun 16, 2024
Download(s)
8
checked on Jun 16, 2024
Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.