Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
From MaRDI portal
Publication:2010087
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.
Recommendations
- Relaxations and discretizations for the pooling problem
- Analysis of MILP techniques for the pooling problem
- A second-order cone programming algorithm for pooling problem
- Pooling problem: alternate formulations and solution methods
- On the effectiveness of sequential linear programming for the pooling problem
Cites work
- A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem
- An exact reformulation algorithm for large nonconvex nLPs involving bilinear terms
- Cones of diagonally dominant matrices
- CONOPT—A Large-Scale GRG Code
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Global minimization by reducing the duality gap
- Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
- Latest Developments in the SDPA Family for Solving Large-Scale SDPs
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Relaxations and discretizations for the pooling problem
- Second order cone programming relaxation of nonconvex quadratic optimization problems
- Semidefinite optimization
- Solving semidefinite-quadratic-linear programs using SDPT3
- Some properties of regularization and penalization schemes for MPECs
- Strong formulations for the pooling problem
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(6)- Tightening methods based on nontrivial bounds on bilinear terms
- Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
- Relaxations and discretizations for the pooling problem
- Exact SDP relaxations for quadratic programs with bipartite graph structures
- 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
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)
