# New SOCP relaxation and branching rule for bipartite bilinear programs

arXiv: https://arxiv.org/abs/1803.09266 · HTML: https://mlsanity.com/paper/1803.09266/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2018.

## Built on by (most cited first, 1 of 1)

- [Formal Verification of Markov Processes with Learned Parameters](https://mlsanity.com/paper/2501.15767/) (2025)

## Abstract (arXiv)

A bipartite bilinear program (BBP) is a quadratically constrained quadratic optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than the standard SDP relaxation intersected with the boolean quadratic polytope. We then propose a new branching rule inspired by the construction of the SOCP relaxation. We describe a new application of BBP called as the finite element model updating problem, which is a fundamental problem in structural engineering. Our computational experiments on this problem class show that the new branching rule together with an polyhedral outer approximation of the SOCP relaxation outperforms a state-of-the-art commercial global solver in obtaining dual bounds.