Optimization Online


A Finitely Convergent Disjunctive Cutting Plane Algorithm for Bilinear Programming

Hamed Rahimian (hrahimi***at***clemson.edu)
Sanjay Mehrotra (mehrotra***at***northwestern.edu)

Abstract: 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(2): 359-413, 2011] and Fampa and Lee [2018], 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 extends the work of Owen and Mehrotra [Math. Prog. 89(3): 437-448, 2001] for solving mixed-integer linear programs to the general bilinear programs.

Keywords: Bilinear programming, Nonconvex programming, Disjunctive programming,Global optimization, Cutting planes

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Rahimian, H. and S. Mehrotra (2020). A finitely convergent disjunctive cutting plane algorithm for bilinear programming. Technical report, Northwestern University.

Download: [PDF]

Entry Submitted: 01/31/2020
Entry Accepted: 01/31/2020
Entry Last Modified: 12/30/2020

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