Optimization Online


Disjoint Bilinear Programming: A Two-Stage Robust Optimization Perspective

Jianzhe Zhen (jianzhe.zhen***at***epfl.ch)
Ahmadreza Marandi (a.marandi***at***tue.nl)
Dick den Hertog (D.denHertog***at***uvt.nl)
Lieven Vandenberghe (vandenbe***at***ucla.edu)

Abstract: 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.

Keywords: Bilinear programming, linear decision rules, Fourier-Motzkin elimination, reformulation-linearization technique.

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 06/29/2018
Entry Accepted: 06/29/2018
Entry Last Modified: 10/10/2018

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