Optimization Online


Solving Mixed Integer Bilinear Problems using MILP formulations

Akshay Gupte (akshayg***at***gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Myun Seok Cheon (myun-seok.cheon***at***exxonmobil.com)
Santanu S. Dey (santanu.dey***at***isye.gatech.edu)

Abstract: In this paper, we examine a mixed integer linear programming (MIP) reformulation for mixed integer bilinear problems where each bilinear term involves the product of a nonnegative integer variable and a nonnegative continuous variable. This reformulation is obtained by first replacing a general integer variable with its binary expansion and then using McCormick envelopes to linearize the resulting product of continuous and binary variables. We present the convex hull of the underlying mixed integer linear set. The effectiveness of this reformulation and associated facet-defining inequalities are computationally evaluated on five classes of instances.

Keywords: bilinear, McCormick envelopes, binary expansion, sequential knapsack, cutting planes, integer programming

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

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

Citation: SIAM Journal on Optimization 23 (2), 721-744, 2013.

Download: [PDF]

Entry Submitted: 07/05/2011
Entry Accepted: 07/05/2011
Entry Last Modified: 07/17/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