A symmetrical linear maxmin approach to disjoint bilinear programming

The disjoint bilinear programming problem can be reformulated using two distinct linear maxmin programming problems. There is a simple bijection between the optimal solutions of the reformulations and the bilinear problem. Moreover, the number of local optima of the reformulations is less than or equal to that of the bilinear problem. In that sense, the reformulations do not introduce additional complexity. Necessary optimality conditions (complementarity and monotonicity) of both reformulations are used to obtain a finitely convergent and exact branch and bound algorithm for the bilinear problem. Determining if the optimal value of a bilinear programming problem is bounded is shown to be strongly NP-complete. The proposed algorithm may be used to answer this question.