Optimization Online


A Finitely Convergent Disjunctive Cutting Plane Algorithm for Bilinear Programming

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

Abstract: We develop a finitely convergent disjunctive cutting plane algorithm to obtain an $\epsilon$-optimal solution or detect infeasibility of a general nonconvex continuous bilinear program. While our cutting planes are obtained in a similar manner to Saxena et al. (2010) and Fampa and Lee (2018), a feature of our algorithm that guarantees the finite convergence is exploring near-optimal extreme point solutions to a current relaxation at each iteration. In this sense, our proposed algorithm extends the idea analyzed in Owen and Mehrotra (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: 02/13/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