Simultaneous convexification of bilinear functions over polytopes with application to network interdiction

Danial Davarnia, Jean Philippe P. Richard, Mohit Tawarmalani

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We study the simultaneous convexification of graphs of bilinear functions gk(x; y) = yAkx over x ∈ Ξ = {x ∈ [0, 1]n |Ex ≥ f} and y ∈ ∆m = {y ∈ Rm+ |1y ≤ 1}. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied to derive convex and concave envelopes of certain bilinear functions, to study unary expansions of integer variables in mixed integer bilinear sets, and to obtain convex hulls of sets with complementarity constraints. Exploiting the structure of Ξ, the procedure naturally yields stronger linearizations for bilinear terms in a variety of practical settings. In particular, we demonstrate the effectiveness of the approach by strengthening the traditional dual formulation of network interdiction problems and report encouraging preliminary numerical results.

Original languageEnglish (US)
Pages (from-to)1801-1833
Number of pages33
JournalSIAM Journal on Optimization
Volume27
Issue number3
DOIs
StatePublished - 2017
Externally publishedYes

Bibliographical note

Funding Information:
∗Received by the editors March 16, 2016; accepted for publication (in revised form) May 3, 2017; published electronically August 17, 2017. http://www.siam.org/journals/siopt/27-3/M106616.html Funding: This work was supported by NSF CMMI grants 1234897 and 1235236. †Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611-6595 (d.davarnia@ufl.edu, richard@ise.ufl.edu). ‡Krannert School of Management, Purdue University, West Lafayette, IN 47907-2076 (mtawarma@purdue.edu).

Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics

Keywords

  • Bilinear functions
  • Convex hulls
  • Cutting planes
  • Envelopes
  • Network interdiction

Fingerprint

Dive into the research topics of 'Simultaneous convexification of bilinear functions over polytopes with application to network interdiction'. Together they form a unique fingerprint.

Cite this