zbMATH — the first resource for mathematics

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.

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX Cite
Full Text: DOI