Optimization Online


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

Danial Davarnia (ddavarni***at***andrew.cmu.edu)
Jean-Philippe Richard (richard***at***ise.ufl.edu)
Mohit Tawarmalani (mtawarma***at***purdue.edu)

Abstract: We study the simultaneous convexification of graphs of bilinear functions that contain bilinear products between variables x and y, where x belongs to a general polytope and y belongs to a simplex. 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 polytopes in the domain, 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

Category 1: Global Optimization (Theory )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Network Optimization

Citation: https://doi.org/10.1137/16M1066166


Entry Submitted: 02/15/2017
Entry Accepted: 02/16/2017
Entry Last Modified: 09/15/2017

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