Solving sparse separable bilinear programs using lifted bilinear cover inequalities

arXiv2208.00345MaRDI QIDQ6406562FDOQ6406562

Authors: Xiaoyi Gu, Santanu S. Dey, Jean-Philippe Richard 

Publication date: 30 July 2022

Abstract: Recently, we proposed a class of inequalities called lifted bilinear cover inequalities, which are second-order cone representable convex inequalities, and 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 semi-definite 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 to when they are not.

This page was built for publication: Solving sparse separable bilinear programs using lifted bilinear cover inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406562)