Optimization Online


New SOCP relaxation and branching rule for bipartite bilinear programs

Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Asteroide Santana(asteroide.santana***at***gatech.edu)
Yang Wang(yang.wang***at***ce.gatech.edu)

Abstract: 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.


Category 1: Global Optimization (Theory )

Category 2: Global Optimization (Applications )


Download: [PDF]

Entry Submitted: 03/25/2018
Entry Accepted: 03/26/2018
Entry Last Modified: 03/25/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society