Simplifying Optimization Problems Before Solving Them
I contribute to presolve, Matteo Santamaria’s Rust library for convex quadratic and conic optimization. My work focuses on constructing and testing reduction examples, tracing their mathematical effects, and explaining the reductions in documentation.
Presolve transforms a problem into a simpler equivalent problem before a numerical solver sees it. Postsolve then maps the reduced solution back to the original variables and constraints. Both directions matter: removing a variable is useful only if its value and the associated solution information can be recovered correctly.
RepositoryReduction rulesPostsolve documentation
A small worked example
A linear program is a special case of the library’s problem model. Consider two variables, with one already fixed by its bounds:
| Original problem | Reduced problem |
|---|---|
| Minimize 3x + y | Minimize 6 + y |
| x = 2 | Eliminate x |
| 3x + y ≤ 10 | y ≤ 4 |
| y ≥ 1 | 1 ≤ y ≤ 4 |
First, substitute the fixed variable. With x = 2, the constraint becomes 6 + y ≤ 10. The objective becomes 6 + y. The constant offset of 6 must be retained when reporting the original objective value.
Then, turn the remaining row into a bound. The constraint y ≤ 4 involves only one variable, so it can be represented as an upper bound rather than a matrix row. Combined with the existing lower bound, the reduced problem is simply to minimize 6 + y over [1, 4].
The transformation removes one variable and replaces a linear constraint with a bound. This is a mathematical illustration of the documented rules, rather than output from a benchmark run.
Recovering the original solution
The reduced optimum is y = 1. Restoring x = 2 gives the original point (2, 1), with objective value 7. The original constraint is satisfied because 3 × 2 + 1 = 7 ≤ 10.
In the library, transformations record recovery information on a tape. Reversing that tape restores eliminated variables and solution information in the original coordinates. The documented API also supports recovering dual multipliers and certificates; those are library capabilities, beyond the simple primal example above.
The distinction matters when checking correctness: a smaller model is only part of the result. The recovered point must also satisfy the original problem, and any objective offsets must be accounted for.
What I examine in reduction examples
- Equivalent constraints: verify that substitutions and bound changes preserve the intended feasible region.
- Sign handling: a singleton row such as 2 ≤ −2x ≤ 6 becomes −3 ≤ x ≤ −1; dividing by a negative coefficient reverses the inequalities.
- Contradictions: incompatible bounds should be recognized as infeasible rather than passed along as a valid reduced model.
- Recovery: restore eliminated variables and check the objective and constraints in the original coordinates.
The full library goes beyond these local rules, with bound propagation, equality substitution, sparse-matrix reductions, and cone-specific transformations. Its rule catalog describes their applicability and numerical safeguards.
The worked example is explanatory. Library behavior and capabilities are described in the linked repository; no performance measurements are claimed here.