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 ay can be much tighter when computed over a strict, nonrectangular subset of the box. In order to exploit this in practice, we propose computing 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 evaluations 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.