  In this work, we propose a two-stage approach to strengthen piecewise
McCormick relaxations for mixed-integer nonlinear programs (MINLP) with
multi-linear terms. In the first stage, we exploit Constraint Programing (CP)
techniques to contract the variable bounds. In the second stage we partition
the variables domains using a dynamic multivariate partitioning scheme. Instead
of equally partitioning the domains of variables appearing in multi-linear
terms, we construct sparser partitions yet tighter relax- ations by iteratively
partitioning the variable domains in regions of interest. This approach
decouples the number of partitions from the size of the variable domains, leads
to a significant reduction in computation time, and limits the number of binary
variables that are introduced by the partitioning. We demonstrate the
performance of our algorithm on well-known benchmark problems from MINLPLIB and
discuss the computational benefits of CP-based bound tightening procedures.
