7275
eng
reportzib
0
--
2019-03-13
--
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.
1438-0064
urn:nbn:de:0297-zib-72759
Benjamin Müller
Benjamin Müller
Felipe Serrano
Ambros Gleixner
ZIB-Report
19-15
eng
uncontrolled
mixed-integer quadratically constrained programs
eng
uncontrolled
nonconvex
eng
uncontrolled
global optimization
eng
uncontrolled
separation
eng
uncontrolled
propagation
eng
uncontrolled
projection
eng
uncontrolled
bilinear terms
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
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/7275/ZR-19-15.pdf