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

Masaki Kimizuka; Sunyoung Kim; Makoto Yamashita

doi:10.1007/s10898-019-00795-w

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

Masaki Kimizuka, Sunyoung Kim, Makoto Yamashita

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

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.

Original language	English
Pages (from-to)	631-654
Number of pages	24
Journal	Journal of Global Optimization
Volume	75
Issue number	3
DOIs	https://doi.org/10.1007/s10898-019-00795-w
State	Published - 1 Nov 2019

Bibliographical note

Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords

Computational efficiency
Linear programming relaxation
Pooling problem
Rescheduling method
Second order cone relaxation
Semidefinite relaxation

Access to Document

10.1007/s10898-019-00795-w

Cite this

@article{ac3f31c1b0294900a9a6a997918a6154,

title = "Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods",

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 = "Computational efficiency, Linear programming relaxation, Pooling problem, Rescheduling method, Second order cone relaxation, Semidefinite relaxation",

author = "Masaki Kimizuka and Sunyoung Kim and Makoto Yamashita",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2019",

month = nov,

day = "1",

doi = "10.1007/s10898-019-00795-w",

language = "English",

volume = "75",

pages = "631--654",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "3",

}

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

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

SN - 0925-5001

VL - 75

SP - 631

EP - 654

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 3

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this