  The most important ingredient for solving mixed-integer nonlinear programs
(MINLPs) to global epsilon-optimality with spatial branch and bound is a tight,
computationally tractable relaxation. Due to both theoretical and practical
considerations, relaxations of MINLPs are usually required to be convex.
Nonetheless, current optimization solver can often successfully handle a
moderate presence of nonconvexities, which opens the door for the use of
potentially tighter nonconvex relaxations. In this work, we exploit this fact
and make use of a nonconvex relaxation obtained via aggregation of constraints:
a surrogate relaxation. These relaxations were actively studied for linear
integer programs in the 70s and 80s, but they have been scarcely considered
since. We revisit these relaxations in an MINLP setting and show the
computational benefits and challenges they can have. Additionally, we study a
generalization of such relaxation that allows for multiple aggregations
simultaneously and present the first algorithm that is capable of computing the
best set of aggregations. We propose a multitude of computational enhancements
for improving its practical performance and evaluate the algorithm's ability to
generate strong dual bounds through extensive computational experiments.
