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

Masaki Kimizuka, Sunyoung Kim, Makoto Yamashita

Research output: Contribution to journalArticlepeer-review

2 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 languageEnglish
Pages (from-to)631-654
Number of pages24
JournalJournal of Global Optimization
Volume75
Issue number3
DOIs
StatePublished - 1 Nov 2019

Keywords

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

Fingerprint

Dive into the research topics of 'Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods'. Together they form a unique fingerprint.

Cite this