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

Dey, Santanu S. and Kocuk, Burak and Santana, Asteroide (2020) Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem. Journal of Global Optimization, 77 (2). pp. 227-272. ISSN 0925-5001 (Print) 1573-2916 (Online)

This is the latest version of this item.

[thumbnail of Dey2020_Article_ConvexificationsOfRank-one-bas.pdf] PDF
Dey2020_Article_ConvexificationsOfRank-one-bas.pdf
Restricted to Registered users only

Download (643kB) | Request a copy

Abstract

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.
Item Type: Article
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Burak Kocuk
Date Deposited: 12 May 2020 16:17
Last Modified: 26 Apr 2022 10:14
URI: https://research.sabanciuniv.edu/id/eprint/39881

Available Versions of this Item

Actions (login required)

View Item
View Item