Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods

Masaki Kimizuka (), Sunyoung Kim () and Makoto Yamashita ()
Additional contact information
Masaki Kimizuka: Tokyo Institute of Technology
Sunyoung Kim: Ewha W. University
Makoto Yamashita: Tokyo Institute of Technology

Journal of Global Optimization, 2019, vol. 75, issue 3, No 3, 654 pages

Abstract: Abstract The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For the pooling problem with time discretization, we propose second order cone programming (SOCP) and linear programming (LP) relaxations and prove that they obtain the same optimal value as the semidefinite programming relaxation. Moreover, a rescheduling method is proposed to efficiently refine the solution obtained by the SOCP or LP relaxation. The efficiency of the SOCP and the LP relaxation and the proposed rescheduling method is illustrated with numerical results on the test instances from the work of Nishi in 2010, some large instances and Foulds 3, 4 and 5 test problems.

Keywords: Pooling problem; Semidefinite relaxation; Second order cone relaxation; Linear programming relaxation; Rescheduling method; Computational efficiency; 90C20; 90C22; 90C25; 90C26 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00795-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:75:y:2019:i:3:d:10.1007_s10898-019-00795-w

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00795-w

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().