Variable aggregation for nonlinear optimization problems

Sakshi Naik

doi:10.1007/s12532-026-00345-y

Variable aggregation for nonlinear optimization problems

2026-11-10

0

PRE

AI

DOI：10.1007/s12532-026-00345-y

Original

Save

Abstract

En 中文

Variable aggregation has been studied as an important pre-solve algorithm for optimization of linear and mixed-integer programs. Although some nonlinear solvers and algebraic modeling languages implement variable aggregation as a pre-solve reduction, the impact it can have on constrained nonlinear programs is unexplored. In this work, we formalize variable aggregation as a pre-solve algorithm to develop reduced-space formulations of nonlinear programs. A novel approximate maximum variable aggregation strategy is developed to aggregate as many variables as possible and compared with aggregation strategies that preserve problem structure. We show that aggregation improves convergence reliability on three test problems and that the improvement is larger for more aggressive aggregation strategies that are allowed to propagate nonlinearities to new constraints. Linearity-preserving methods converge up to 29 more problem instances (out of 363 total instances), while more aggressive methods converge up to 54 more instances. Our conservative, structure-preserving aggregation methods improve solve time by up to a factor of 6, but more aggressive aggregation methods slow down Hessian evaluation due to larger nonlinear expressions. With the most aggressive aggregation method, Hessian evaluation takes up to 75% of the total solve time. We recommend that algorithm developers implement options for linearity-preserving aggregation and greedy approximate-maximum aggregation (which is the most reliable among methods we consider). The former prioritizes solve time, while the latter prioritizes reliability. Combined, they approximate the virtual best of all six aggregation strategies considered in this paper.

Keywords:

Nonlinear optimization

Presolve

Graph theory

Variable aggregation for nonlinear optimization problems

Abstract

Journal

Organization

Cited Papers