💻 computer science

Variable aggregation for nonlinear optimization problems

This paper formalizes variable aggregation as a pre-solve algorithm for nonlinear programs, introducing a novel approximate maximum strategy that generally improves convergence reliability and solve time, though it may create Hessian evaluation bottlenecks when significantly increasing nonlinear variable counts.

Original authors: Sakshi Naik, Lorenz Biegler, Russell Bent, Robert Parker

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sakshi Naik, Lorenz Biegler, Russell Bent, Robert Parker

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, tangled knot of string. This knot represents a complex mathematical problem used by engineers and scientists to design things like oil refineries, power grids, or chemical reactors. The goal is to find the "perfect" setting for every single string (variable) to make the whole system work as efficiently as possible.

This paper is about a clever trick to untangle that knot before you even start trying to solve it. The authors call this trick "Variable Aggregation."

Here is the breakdown of their work using simple analogies:

1. The Problem: The Tangled Knot

In these complex systems, you have thousands of variables (like temperature, pressure, flow rates) and thousands of rules (equations) connecting them.

The Issue: Sometimes, a rule says, "Variable A is exactly equal to 2 times Variable B plus 5."
The Old Way: You keep both A and B in your knot, even though you know exactly how they relate. This makes the knot bigger and harder to pull tight.
The New Way (Aggregation): You realize, "Hey, I don't need Variable A anymore! I can just replace it with '2 times B plus 5' everywhere A appears." You cut A out of the knot and tie the string directly to B. This is Variable Aggregation.

2. The Strategy: How to Cut the Knot

The authors realized that while this trick is great for simple math problems (like linear ones), it's risky for complex, non-linear problems (like the ones in chemical engineering). If you cut too aggressively, you might accidentally create a new, even messier knot.

They tested several different "scissors" (algorithms) to see which ones worked best:

The "Snip-Only-Loose-Ends" Strategy (Conservative): This method only cuts out variables that are very simple (like "A = 5"). It's safe and doesn't change the shape of the knot much, but it doesn't untangle much either.
The "Cut-Everything-You-Can" Strategy (Aggressive): This method tries to cut out as many variables as possible, even if it means the remaining strings get thicker and more tangled. It's like trying to untangle a knot by yanking on every loose end at once.
The "Smart-Cut" Strategy (Structure-Preserving): This is the paper's sweet spot. It cuts out variables but ensures that the remaining strings don't get too thick or complicated. It's like carefully snipping a specific loop so the rest of the knot stays neat.

3. The Results: What Happened?

The researchers tested these strategies on four real-world "knots" (a distillation column, a chemical reactor, a gas pipeline, and a power grid). Here is what they found:

Reliability (The "Will it work?" Test):
Imagine you are trying to walk through a maze. Sometimes, the maze is so confusing you get stuck.
- Finding: Using these aggregation tricks made the maze much easier to navigate. The "Smart-Cut" and "Aggressive" strategies helped the computer solver find the exit (the solution) much more often than the original, uncut knot. It's like giving the solver a map that removes dead ends.
Speed (The "How fast?" Test):
- Finding: Sometimes, cutting the knot made the solver run faster because there were fewer strings to manage.
- The Catch: However, if you cut too aggressively (the "Cut-Everything" strategy), the remaining strings became so thick and complex that calculating their shape took forever. It's like removing 90% of the knots, but the remaining 10% are now made of steel cables instead of string. The computer got stuck trying to calculate the weight of those steel cables.

4. The Big Takeaway

The paper concludes that Variable Aggregation is a powerful tool, but you have to use the right scissors.

Don't be too timid: Cutting out a few variables helps.
Don't be too greedy: Cutting out everything can backfire and slow you down.
The Winner: The "Smart-Cut" strategy (specifically the Degree-2 method) was the best all-rounder. It removed enough variables to make the problem easier to solve and more reliable, without making the remaining math too heavy to handle.

In a Nutshell

Think of this paper as a guide for a mechanic fixing a car engine.

Before: The mechanic was trying to tune an engine with 1,000 loose wires, many of which were just duplicates of others.
The Fix: The mechanic realized, "I can remove 400 of these wires and just tape the remaining ones together in a smarter way."
The Result: The engine started more reliably (convergence) and ran smoother (speed), as long as the mechanic didn't tape the wires together in a way that created a giant, heavy ball of wire that blocked the airflow.

The authors are essentially saying: "Yes, you should simplify your math problems by removing redundant variables, but do it carefully so you don't create a new kind of mess."

1. Problem Statement

The paper addresses the challenge of improving the convergence reliability and solve time of Nonlinear Programs (NLPs). While variable aggregation (substituting variables defined by equality constraints into other equations) is a well-established pre-solve technique for Linear and Mixed-Integer Linear Programming (MILP), its application and impact on constrained nonlinear programs are not well-documented.

Existing solvers and modeling languages (e.g., AMPL, Pyomo, AIMMS) implement some form of variable aggregation, but often with limited heuristics (e.g., only linear constraints with two variables). The authors aim to formalize variable aggregation as a pre-solve algorithm for NLPs, exploring how different aggregation strategies affect:

Problem Structure: Density of Jacobian and Hessian matrices.
Runtime: Total solve time and the breakdown of computational costs (function evaluation, Jacobian, Hessian, KKT factorization).
Convergence Reliability: The ability of interior-point solvers (specifically IPOPT) to find a solution across a wide range of parameter values.

2. Methodology

Mathematical Formulation

The authors define variable aggregation as a reduction of the NLP problem space. Given a problem with equality constraints $g(z)=0$ , if a subset of variables $v$ and constraints $\tilde{g}(u, v)=0$ can be identified such that the Jacobian $\nabla_v \tilde{g}$ is nonsingular, the Implicit Function Theorem allows $v$ to be expressed as $v = \tilde{g}_v(u)$ . Substituting this back eliminates $v$ and the corresponding constraints, creating a reduced-space formulation.

To ensure this can be done explicitly (without iterative equation solving), the authors rely on Lemma 1: A subset of constraints can be eliminated if the defining functions form a strictly lower triangular Jacobian structure. This corresponds to finding a matching in a bipartite graph of variables and constraints that induces a lower triangular incidence matrix.

Aggregation Strategies

The paper proposes and compares six distinct aggregation methods, categorized into two groups:

A. Structure-Preserving Strategies (Conservative)
These methods limit the complexity of the resulting expressions to prevent density spikes.

LD1 (Linear Degree-1): Aggregates fixed variables (e.g., $y = c$ ).
ECD2 (Equal Coefficient Degree-2): Aggregates variables using linear constraints with two variables where coefficients have equal magnitude (e.g., $y = x + c$ ). Preserves Jacobian entries.
LD2 (Linear Degree-2): Aggregates variables using linear constraints with two variables (e.g., $y = ax + b$). Preserves linearity.
D2 (Degree-2): Aggregates variables using constraints with at most two variables, where at least one appears linearly. Allows non-linearities but limits variable count per constraint.

B. Approximate Maximum Strategies (Aggressive)
These methods aim to eliminate the maximum number of variables possible, potentially increasing problem density.
5. GR (Greedy): Iterates through constraints, adding a variable-constraint pair if the variable appears linearly and hasn't been used in a way that breaks lower triangularity.
6. LM (Linear Matching): A novel heuristic.
* Computes a maximum matching on the linear bipartite graph.
* Constructs the subgraph induced by this matching (including nonlinear edges).
* Performs block triangularization on this subgraph.
* Applies the greedy heuristic within each diagonal block to extract a lower-triangular subset.
* Theoretical Bound: Theorem 2 proves the number of eliminations is bounded by the size of the block partition (lower bound) and the maximum linear matching (upper bound).

Experimental Setup

Solver: IPOPT (Interior Point OPTimizer).
Test Problems: Four distinct NLPs:
1. Distillation Column: Dynamic optimization with bilinear/rational terms.
2. Moving Bed Reactor: Steady-state chemical reactor with multilinear/rational terms.
3. Pipeline Network: Dynamic gas transport optimization.
4. AC Optimal Power Flow (ACOPF): Large-scale power grid optimization (4,917 buses).
Reliability Testing: For three of the four problems, a parameter sweep was conducted (121 parameter combinations per problem) to measure the percentage of instances successfully converged within 3,000 iterations.

3. Key Contributions

Formalization: Provided a formal sufficient condition (strictly lower triangular Jacobian via bipartite matching) for explicit variable aggregation in NLPs.
Novel Algorithm: Developed the Linear Matching (LM) algorithm, which uses graph theory (maximum matching and block triangularization) to approximate the maximum set of eliminable variables.
Comprehensive Analysis: Systematically compared conservative (structure-preserving) vs. aggressive (approximate maximum) strategies across structural properties, runtime, and reliability.
Empirical Evidence: Demonstrated that while aggressive aggregation can increase Hessian evaluation costs, it often significantly improves convergence reliability, a trade-off previously unquantified.

4. Results

Structural Impact

Variable Elimination: Aggressive methods (GR, LM) eliminated 70–90% of variables in some models, whereas structure-preserving methods (LD1, LD2, D2) eliminated <60%.
Density: Structure-preserving methods maintained the average number of non-zeros (NNZ) per constraint. Aggressive methods significantly increased density and the number of nonlinear terms per constraint.
Hessian Complexity: Aggressive aggregation led to more complex expression graphs, increasing the number of nonlinear non-zeros in the Hessian.

Runtime Performance

Trade-off: Reducing the problem size (fewer variables) speeds up KKT matrix factorization ("Other" time). However, increased density and nonlinearity slow down Hessian evaluation.
Bottlenecks: For the Pipeline and Distillation problems, aggressive aggregation (LM) increased the time spent in Hessian evaluation to 75% of the total solve time, becoming the new bottleneck.
Net Effect:
- Distillation & Pipeline: Aggregation generally reduced total solve time.
- OPF: Aggregation increased solve time (due to increased inequality constraints from bounded variables and iteration count).
- Moving Bed: Minimal impact on total time.

Convergence Reliability

General Improvement: Variable aggregation consistently improved convergence reliability across all test problems. No method performed worse than the original unaggregated model.
Magnitude: The best strategies (D2, GR, LM) improved convergence rates by 13–15% compared to the original model.
- Example: In the Distillation problem, the D2 strategy achieved 100% convergence, whereas the original model only solved 85% of instances.
Mechanism: The authors hypothesize that aggregated formulations keep primal iterates closer to the feasible set of the original problem, resulting in better-conditioned KKT matrices and avoiding the "infeasible paths" that cause standard solvers to fail.

5. Significance and Conclusion

Reliability over Speed: The paper highlights that while aggressive aggregation can introduce computational bottlenecks (Hessian evaluation), the gain in convergence reliability is often the more critical factor for robust optimization.
Recommendation: The authors recommend the Degree-2 (D2) strategy as a general pre-solve default. It strikes an optimal balance: it eliminates a significant number of variables (improving reliability) without drastically increasing problem density or Hessian complexity.
Future Work: The authors suggest implementing these as standard pre-solve options in modeling languages (like Pyomo/AMPL) and call for theoretical analysis on how aggregation interacts with global convergence methods (line search, trust regions) to explain the observed reliability improvements.

In summary, this work establishes variable aggregation as a critical, yet underutilized, pre-solve step for nonlinear optimization, proving that reducing the problem dimension—even at the cost of some structural complexity—can make difficult NLPs solvable where they previously failed.