TY - JOUR
A1 - MÃ¼ller, Benjamin
A1 - Serrano, Felipe
A1 - Gleixner, Ambros
T1 - Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms
T2 - SIAM Journal on Optimization
N2 - One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly.
Y1 - 2020
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7276
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-72767
VL - 30
IS - 2
SP - 1339
EP - 1365
ER -