Optimization Online


Solving Pooling Problems by LP and SOCP Relaxations and Rescheduling Methods

Masaki Kimizuka(kimi3masa0***at***gmail.com)
Sunyoung Kim(skim***at***ewha.ac.kr)
Makoto Yamashita(makoto.yamashita***at***is.titech.ac.jp)

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 P-formulation of 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. The equivalence among the optimal values of the three relaxations is also computationally shown. 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, 5 test problems.

Keywords: Pooling problem, Semidefinite relaxation, Second order cone relaxation, Linear programming relaxation, Rescheduling method, Computational efficiency.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Applications -- Science and Engineering

Citation: B-487, Research report, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 04/09/2018
Entry Accepted: 04/09/2018
Entry Last Modified: 04/09/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society