Tightening methods based on nontrivial bounds on bilinear terms

Research output: Contribution to journalArticlepeer-review

Abstract

We develop tightening and solution methods for optimization problems containing bilinear terms. We focus on the bilinear term w= xy with nonnegative variables x∈ [xL, xU] and y∈ [yL, yU] , where w is semi-continuous and upper and lower bounded by wU and wL when positive. wU and wL are said to be nontrivial upper and lower bounds if wU is smaller than xUyU and wL is greater than xLyL, respectively. We derive a family of valid linear constraints and show that, when one of the nontrivial bounds is active, such constraints are tangent to one branch of the hyperbola that represents the bilinear term. We propose different preprocessing methods for generating strong constraints from the family. Computational results demonstrate the effectiveness of the proposed methods in terms of reducing optimality gap and computational time.

Original languageEnglish (US)
JournalOptimization and Engineering
DOIs
StateAccepted/In press - 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Civil and Structural Engineering
  • Aerospace Engineering
  • Mechanical Engineering
  • Control and Optimization
  • Electrical and Electronic Engineering

Keywords

  • Nonconvex optimization
  • Nonlinear optimization
  • Preprocessing
  • Semi-continuous variables
  • Valid constraints

Fingerprint

Dive into the research topics of 'Tightening methods based on nontrivial bounds on bilinear terms'. Together they form a unique fingerprint.

Cite this