Disjoint bilinear programming: a two-stage robust optimization perspective

Jianzhe Zhen, A. Marandi (Corresponding author), Dick den Hertog, Lieven Vandenberghe

Research output: Contribution to journalArticleAcademic

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.
Original languageEnglish
Number of pages34
JournalOptimization Online
Publication statusPublished - 2018

Keywords

  • bilinear programming
  • linear decision rules
  • Fourier-Motzkin elimination
  • reformulation-linearization technique

Fingerprint

Dive into the research topics of 'Disjoint bilinear programming: a two-stage robust optimization perspective'. Together they form a unique fingerprint.

Cite this