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

Santanu S. Dey (), Burak Kocuk () and Asteroide Santana ()
Additional contact information
Santanu S. Dey: Georgia Institute of Technology
Burak Kocuk: Sabancı University
Asteroide Santana: Georgia Institute of Technology

Journal of Global Optimization, 2020, vol. 77, issue 2, No 2, 227-272

Abstract: Abstract We study sets defined as the intersection of a rank-one 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-one 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-one perspective, we propose new rank-one 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.

Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00844-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-019-00844-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00844-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().