Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities

Xiaoyi Gu (), Santanu S. Dey () and Jean-Philippe P. Richard ()
Additional contact information
Xiaoyi Gu: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Santanu S. Dey: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Jean-Philippe P. Richard: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455

INFORMS Journal on Computing, 2024, vol. 36, issue 3, 884-899

Abstract: Recently a class of second-order cone representable convex inequalities called lifted bilinear cover inequalities were introduced, which are valid for a set described by a separable bilinear constraint together with bounds on variables. In this paper, we study the computational potential of these inequalities for separable bilinear optimization problems. We first prove that the semidefinite programming relaxation provides no benefit over the McCormick relaxation for such problems. We then design a simple randomized separation heuristic for lifted bilinear cover inequalities. In our computational experiments, we separate many rounds of these inequalities starting from McCormick’s relaxation of instances where each constraint is a separable bilinear constraint set. We demonstrate that there is a significant improvement in the performance of a state-of-the-art global solver in terms of gap closed, when these inequalities are added at the root node compared with when they are not.

Keywords: lifting; separable bilinear sets; nonconvex (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0230 (application/pdf)

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:inm:orijoc:v:36:y:2024:i:3:p:884-899

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().