Citation
Rahimian, H. and S. Mehrotra (2020). A finitely convergent disjunctive cutting plane algorithm for bilinear programming. Technical report, Northwestern University.
A Finitely Convergent Disjunctive Cutting Plane Algorithm for Bilinear Programming
\(\) In this paper we present and analyze a finitely-convergent disjunctive cutting plane algorithm to obtain an \(\epsilon\)-optimal solution or detect infeasibility of a general nonconvex continuous bilinear program. While the cutting planes are obtained in a manner similar to Saxena, Bonami, and Lee [Math. Prog. 130: 359–413, 2011] and Fampa and Lee [J. Global Optim. 80: 287–305, 2021], a feature of the algorithm that guarantees finite convergence is exploring near-optimal extreme point solutions to a current relaxation at each iteration. In this sense, the presented algorithm and its analysis extend the work Owen and Mehrotra [Math. Prog. 89: 437–448, 2001] for solving mixed-integer linear programs to the general bilinear programs.