Disjoint bilinear programming: a two-stage robust optimization perspective

In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem.
We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.