7276
2020
eng
1339
1365
27
2
30
article
0
--
--
--
Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms
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.
SIAM Journal on Optimization
urn:nbn:de:0297-zib-72767
10.1137/19M1249825
yes
2020/01/10
urn:nbn:de:0297-zib-72759
Benjamin Müller
Benjamin Müller
Felipe Serrano
Ambros Gleixner
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Serrano, Felipe
Müller, Benjamin
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
EnBA-M
https://opus4.kobv.de/opus4-zib/files/7276/ZR-19-15.pdf