2022/07/31 by Xiaoyi Gu, Gu, Xiaoyi, Santanu S. Dey +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2208.00345
openalex publication_date 2022/07/31 · openalex created_date 2022/08/03 · openalex updated_date 2026/07/28
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.