  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.
