Optimization Online


Lifting convex inequalities for bipartite bilinear programs

Xiaoyi Gu (xiaoyigu***at***gatech.edu)
Santanu S. Dey (santanu.dey***at***isye.gatech.edu)
Jean-Philippe P. Richard (jrichar***at***umn.edu)

Abstract: The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear constraint together with bounds, it is always possible to sequentially lift a seed inequality that is valid for a restriction obtained by fixing variables to their bounds, when the lifting is accomplished using affine functions of the fixed variables. In this setting, sequential lifting involves solving a non-convex nonlinear optimization problem each time a variable is lifted, just as in Mixed Integer Linear Programming. To reduce the computational burden associated with this procedure, we develop a framework based on subadditive approximations of lifting functions that permits sequence-independent lifting of seed inequalities for separable bipartite bilinear sets. In particular, this framework permits the derivation of closed-form valid inequalities. We then study a separable bipartite bilinear set where the coefficients form a minimal cover with respect to the right-hand-side. For this set, we introduce a bilinear cover inequality, which is second-order cone representable. We argue that this bilinear cover inequality is strong by showing that it yields a constant-factor approximation of the convex hull of the original set. We study its lifting function and construct a two-slope subadditive upper bound. Using this subadditive approximation, we lift fixed variable pairs in closed-form, thus deriving a lifted bilinear cover inequality that is valid for general separable bipartite bilinear sets with box constraints.

Keywords: Lifting Separable bipartite bilinear sets Subadditivity

Category 1: Global Optimization (Theory )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Nonlinear Optimization (Other )


Download: [PDF]

Entry Submitted: 06/01/2021
Entry Accepted: 06/04/2021
Entry Last Modified: 06/04/2021

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