Solving Mixed Integer Bilinear Problems using MILP formulations
Akshay Gupte (akshayggatech.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.
Entry Submitted: 07/05/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|