Skip to main content
Article
Simultaneous convexification of bilinear functions over polytopes with application to network interdiction
SIAM Journal on Optimization (2017)
  • Danial Davarnia, University of Florida
  • Jean-Philippe Richard, University of Florida
  • Mohit Tawarmalani, Purdue University
Abstract
We study the simultaneous convexification of graphs of bilinear functions $g^k({x};{y}) = {y}^{\intercal} A^k {x}$ over ${x} \in \ensuremath{\Xi} = \{ {x} \in [0,1]^n \, | \, E{x} \geq {f} \}$ and ${y} \in \Delta_m = \{ {y} \in {R}_+^{m} \, | \, {1^{\intercal}y} \leq 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 $\Xi$, 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.
Keywords
  • bilinear functions,
  • envelopes,
  • convex hulls,
  • cutting planes,
  • network interdiction
Publication Date
August, 2017
DOI
https://doi.org/10.1137/16M1066166
Publisher Statement
Copyright 2017 Society for Industrial and Applied Mathematics
Citation Information
Danial Davarnia, Jean-Philippe Richard and Mohit Tawarmalani. "Simultaneous convexification of bilinear functions over polytopes with application to network interdiction" SIAM Journal on Optimization Vol. 27 Iss. 3 (2017) p. 1801 - 1833
Available at: http://works.bepress.com/danial-davarnia/2/