×

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.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

Couenne