Solving Pooling Problems 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 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
Entry Submitted: 04/09/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|