Solving mixed integer bilinear problems using MILP formulations. (English) Zbl 1300.90021
The paper considers a mixed integer bilinear program, where every bilinear term involves the product of a nonnegative integer variable and and a nonnegative continuous variable. The objectives and constraints of this program are first linearized, and to obtain MILP formulations, the bilinear terms are further studied. This involves a binary expansion of the integer variables and McCormick envelopes. The authors investigate the binary expansion sets in detail, obtaining facets of their convex hull. They derive a branch and cut algorithm for the MILP reformulation. This algorithm is tested on five classes of instances, showing its effectiveness.
Reviewer: Matthias Ehrgott (Lancaster)
MSC:
90C11 | Mixed integer programming |
90C26 | Nonconvex programming, global optimization |
90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |