TY - JOUR
T1 - Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
AU - Kimizuka, Masaki
AU - Kim, Sunyoung
AU - Yamashita, Makoto
N1 - Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2019/11/1
Y1 - 2019/11/1
N2 - 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.
AB - 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.
KW - Computational efficiency
KW - Linear programming relaxation
KW - Pooling problem
KW - Rescheduling method
KW - Second order cone relaxation
KW - Semidefinite relaxation
UR - http://www.scopus.com/inward/record.url?scp=85067046444&partnerID=8YFLogxK
U2 - 10.1007/s10898-019-00795-w
DO - 10.1007/s10898-019-00795-w
M3 - Article
AN - SCOPUS:85067046444
VL - 75
SP - 631
EP - 654
JO - Journal of Global Optimization
JF - Journal of Global Optimization
SN - 0925-5001
IS - 3
ER -