Strong convex nonlinear relaxations of the pooling problem
From MaRDI portal
Abstract: We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound.
Recommendations
- Analysis of MILP techniques for the pooling problem
- Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
- New multi-commodity flow formulations for the pooling problem
- Relaxations and discretizations for the pooling problem
- Valid Inequalities for the Pooling Problem with Binary Variables
Cites work
- A bilinear approach to the pooling problem†
- A Decomposition Strategy for Global Optimum Search in the Pooling Problem
- A multi-commodity flow formulation for the generalized pooling problem
- A polynomially solvable case of the pooling problem
- Advances for the pooling problem: modeling, global optimization, and computational studies (Survey)
- Analysis of MILP techniques for the pooling problem
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
- Deriving convex hulls through lifting and projection
- Global minimization by reducing the duality gap
- Large-scale standard pooling problems with constrained pools and fixed demands
- New multi-commodity flow formulations for the pooling problem
- Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness
- Pooling problem: alternate formulations and solution methods
- Relaxations and discretizations for the pooling problem
- Strong formulations for the pooling problem
- Successive Linear Programming at Exxon
- The computational complexity of the pooling problem
- Valid Inequalities for the Pooling Problem with Binary Variables
Cited in
(8)- Tightening methods based on nontrivial bounds on bilinear terms
- Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
- Valid Inequalities for the Pooling Problem with Binary Variables
- Analysis of MILP techniques for the pooling problem
- Preprocessing Nonlinear Functional Constraints with Applications to the Pooling Problem
- New multi-commodity flow formulations for the pooling problem
- (Global) optimization: historical notes and recent developments
- Tightening discretization-based MILP models for the pooling problem using upper bounds on bilinear terms
This page was built for publication: Strong convex nonlinear relaxations of the pooling problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114398)
