Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem

This is the latest version of this item.

Official URL: http://dx.doi.org/10.1007/s10898-019-00844-4

We study sets defined as the intersection of a rank-1 constraint with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. In all these cases, we also show that a linear objective can be optimized in polynomial time over these sets. Towards the application side, we show how these sets relate to commonly occurring substructures of a general quadratically constrained quadratic program. To further illustrate the benefit of studying quadratically constrained quadratic programs from a rank-1 perspective, we propose new rank-1 formulations for the generalized pooling problem and use our convexification results to obtain several new convex relaxations for the pooling problem. Finally, we run a comprehensive set of computational experiments and show that our convexification results together with discretization significantly help in improving dual bounds for the generalized pooling problem.