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

DOI10.1007/S10898-019-00795-WzbMATH Open1433.90103arXiv1804.02857OpenAlexW2952789813WikidataQ127713831 ScholiaQ127713831MaRDI QIDQ2010087FDOQ2010087

Masaki Kimizuka, Sunyoung Kim, Makoto Yamashita

Publication date: 3 December 2019

Published in: Journal of Global Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1804.02857

zbMATH Keywords

computational efficiencysemidefinite relaxationpooling problemlinear programming relaxationrescheduling methodsecond-order cone relaxation

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)

Cites Work

• CONOPT—A Large-Scale GRG Code
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solving semidefinite-quadratic-linear programs using SDPT3
• Semidefinite optimization
• Global minimization by reducing the duality gap
• Strong formulations for the pooling problem
• An exact reformulation algorithm for large nonconvex nLPs involving bilinear terms
• Second order cone programming relaxation of nonconvex quadratic optimization problems
• Some properties of regularization and penalization schemes for MPECs
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
• Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
• Cones of diagonally dominant matrices
• Relaxations and discretizations for the pooling problem
• Optimization over structured subsets of positive semidefinite matrices via column generation
• A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem
• Latest Developments in the SDPA Family for Solving Large-Scale SDPs

Cited In (5)

• Tightening discretization-based MILP models for the pooling problem using upper bounds on bilinear terms
• Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging scheduling
• Tightening methods based on nontrivial bounds on bilinear terms
• Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
• Exact SDP relaxations for quadratic programs with bipartite graph structures

Uses Software

• CONOPT
• SDPA
• SeDuMi
• SDPT3
• CPLEX
• SparsePOP
• Mosek
• SPOTless
• GitHub

This page was built for publication: Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010087)