# Tightening McCormick Relaxations for Nonlinear Programs via Dynamic Multivariate Partitioning

arXiv: https://arxiv.org/abs/1606.05806 · HTML: https://mlsanity.com/paper/1606.05806/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2016.

## Built on by (most cited first, 2 of 2)

- [Pushing the limits of fairness impossibility: Who's the fairest of them all?](https://mlsanity.com/paper/2208.12606/) (2022)
- [Simplifying deflation for non-convex optimization with applications in Bayesian inference and topology optimization](https://mlsanity.com/paper/2201.11926/) (2022)

## Abstract (arXiv)

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.