Lifting Convex Inequalities for Bipartite Bilinear Programs

Xiaoyi Gu, Santanu S. Dey, Jean Philippe P. Richard

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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 right-hand-side. For this set, we derive a “bilinear cover inequality”, which is second-order cone representable. We argue that this bilinear covering 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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings
EditorsMohit Singh, David P. Williamson
PublisherSpringer Science and Business Media Deutschland GmbH
Pages148-162
Number of pages15
ISBN (Print)9783030738785
DOIs
StatePublished - 2021
Event22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021 - Virtual, Online
Duration: May 19 2021May 21 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12707 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021
CityVirtual, Online
Period5/19/215/21/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

  • Bipartite bilinear sets
  • Lifting
  • Subadditivity

Fingerprint

Dive into the research topics of 'Lifting Convex Inequalities for Bipartite Bilinear Programs'. Together they form a unique fingerprint.

Cite this