Optimization Online


Some Results on the Strength of Relaxations of Multilinear Functions

James Luedtke (jrluedt1***at***wisc.edu)
Mahdi Namazifar (namazifar***at***wisc.edu)
Jeff Linderoth (linderoth***at***wisc.edu)

Abstract: We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, these relaxations are equivalent if the bounds on all variables are symmetric around zero. We then review and extend some results on conditions when the concave envelope of a multilinear function can be written as a sum of concave envelopes of its individual terms. Finally, for bilinear functions we prove that the difference between the concave overestimator and convex underestimator obtained from the McCormick relaxation approach is always within a constant of the difference between the concave and convex envelopes. These results, along with numerical examples we provide, provide insight into how to construct strong relaxations of multilinear functions.

Keywords: Global optimization, Bilinear function, Multilinear function

Category 1: Global Optimization

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

Citation: Luedtke, J., M. Namazifar and J. Linderoth. Mathematical Programming, 136:325-351, 2012, DOI 10.1007/s10107-012-0606-z


Entry Submitted: 08/13/2010
Entry Accepted: 08/20/2010
Entry Last Modified: 01/02/2013

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