Crate pounce_presolve 

Algorithmic NLP preprocessing exposed as a composable TNLP wrapper.

Tracks pounce issue #20.

• Phase 0 — scaffolding, options table, no-op identity path.

• Phase 1 — Andersen-style bound tightening against linear rows.

• Phase 2 — redundant linear-constraint removal: rows whose activity interval is implied by the (possibly Phase-1-tightened) variable box are dropped from the problem the solver sees, then reinstated with λ=0 when forwarding eval_h / finalize_solution to the inner TNLP.

  Dual attribution (issue M24). A row that was itself the reason a bound got tightened in Phase 1 — e.g. x ≥ 2 tightening x_l = 2 — then has an activity interval flush against its own bound, so Phase 2 sees it as redundant and drops it. If that bound is active at the solution the interior-point method reports the dual on the variable bound multiplier (z_l/z_u) against a bound that did not exist in the original problem. For a singleton row Phase 2 dropped, finalize_solution hands that multiplier back to the row (λ = (z_u − z_l)/a, the bound’s side zeroed), and get_starting_point does the inverse, so the duals agree with a no-presolve solve and a .sol round-trips; see SingletonBound. A declared bound tied with the row keeps the multiplier, row λ = 0 (a degenerate pair: presolve=no’s interior point splits it roughly 1:1, and both are valid KKT points; the rule is “the declared bound is the incumbent”, pinned by tests/presolve_derived_bound_duals.rs).

  Bounds derived from multi-variable rows (Phase 1 / FBBT, e.g. x0 = 2·x1, x0 ≥ 4 ⇒ x1 ≥ 2, or x0 = 0.5 then x0 + x1 ≤ 2 ⇒ x1 ≤ 1.5) are handled by a general postsolve recovery rather than per-derivation provenance: finalize_solution zeroes every multiplier on a derived side (presolve’s bound strictly tighter than the declared one) that the original model does not have active at x*, and re-solves for the original problem’s multipliers on the active rows and declared bounds the leftover stationarity residual reaches — a sign-constrained least squares, dense over that connected component, by a proximal-point iteration started from the reduced solve’s own multipliers (dual_recovery). Where the original multipliers are unique this is exactly the presolve=no answer; where they are not it is a valid KKT multiplier set of the original problem. It runs only when a derived side carries a multiplier, and a component past the dense cap (600 multipliers / 5000 variables) or a solve that does not close stationarity leaves the reduced attribution in place with a warning. Inbound, get_starting_point moves a Phase-2-dropped row’s supplied multiplier onto the reduced bounds of the variables it touches (a_ij·λ_i), so the reduced start is stationary where the supplied one was. A .sol round-trips through warm_start_init_point=yes max_iter=0 under any warm-start push: the recovery above, the singleton hand-back, Phase 0’s frames and linear_eq_elim’s sweep all re-derive multipliers from stationarity at the returned x, which the default push moved 1e-3 off its bounds, so they would be O(push) off the supplied duals. Instead each layer records the warm start it served and, when the solver hands back the served multipliers unchanged, reports the ones it was handed — its inbound map’s exact inverse on that map’s image (warm_echo). A cold solve records none, so its postsolve is the recovery alone. Primal point and objective are unaffected throughout.

• Phase 3 — structural LICQ check on the surviving equality rows. Verdict is published via PresolveTnlp::licq_verdict.

• Phase 4 — bound-multiplier warm-start hints for variables whose bounds were tightened by Phase 1. Hints are emitted on init_z and exposed via PresolveTnlp::z_warm_starts.

• Phase 5 — sensitivity-aware passthrough: projects user-supplied constraint metadata and scaling through the row reduction on the way in, and expands outer→inner on the way out in finalize_metadata.

• Phase 6 — linear-equality variable elimination (presolve_linear_eq_reduction, issue #487). The only phase that removes columns: singleton and two-variable linear equality rows determine variables, which are substituted away and recovered at finalize_solution. It lives in its own wrapper (linear_eq_elim::LinearEqElimTnlp) stacked outside PresolveTnlp, so Phases 0–5 keep working in the variable space they were written against, and it is the outer layer that re-presents the reduced one. Off by default.

Re-exports

pub use block_solve::BlockEquations;

pub use block_solve::BlockSolveError;

pub use block_solve::BlockSolveOptions;

pub use block_solve::BlockSolveOutcome;

pub use block_solve::BlockSolver;

pub use block_solve::DampedNewtonSolver;

pub use bound_tighten::INF_BOUND;

pub use bound_tighten::LinearRow;

pub use bound_tighten::TightenReport;

pub use bound_tighten::tighten_bounds;

pub use btf::BlockTriangularBlock;

pub use btf::BlockTriangularForm;

pub use components::SquareComponent;

pub use components::SquareComponents;

pub use coupling::AuxiliaryCouplingClass;

pub use coupling::classify_block;

pub use coupling::objective_gradient_support;

pub use diagnostics::AuxiliaryPreprocessingDiagnostics;

pub use diagnostics::AuxiliaryRejectionReason;

pub use dulmage_mendelsohn::DMPart;

pub use dulmage_mendelsohn::DulmageMendelsohnPartition;

pub use incidence::EqualityIncidence;

pub use incidence::InequalityIncidence;

pub use incidence::ProbeView;

pub use licq::EqRow;

pub use licq::LicqVerdict;

pub use licq::licq_check;

pub use linear_eq_elim::FullSolution;

pub use linear_eq_elim::LinearEqElimTnlp;

pub use linear_eq_elim::recover_dropped_multipliers;

pub use linear_eq_plan::ElimStep;

pub use linear_eq_plan::EliminationPlan;

pub use linear_eq_plan::LinearEqElimReport;

pub use linear_eq_plan::PlanConfig;

pub use linear_eq_plan::PlanInput;

pub use linear_eq_plan::VarRecovery;

pub use linear_eq_plan::build_plan;

pub use options::AuxiliaryCouplingPolicy;

pub use options::LicqAction;

pub use options::PresolveOptions;

pub use options::register_options;

pub use reduction_frame::ReductionFrame;

pub use reduction_frame::ReductionStack;

pub use redundant::find_redundant_rows;

pub use warm::PresolveFingerprint;

pub use warm::PresolveMap;

pub use warm::ProjectedWarm;

pub use warm::WarmPoint;

pub use warm::WarmProjectionReport;

pub use warm::clamp_seed;

pub use warm::compute_fingerprint;

pub use warm::project_warm_point;

pub use warm::project_warm_point_full;

Modules

auxiliary

Phase-0 orchestrator for auxiliary-equality preprocessing.

block_solve

Lightweight damped-Newton solver for square ≤ 8-dim auxiliary blocks, plus the BlockSolver trait for the larger-block fallback.

bound_tighten

Phase 1 — bound tightening via constraint propagation.

btf

Tarjan SCC + topological order → block-triangular form on each connected component of the square-matched part.

components

Weakly-connected component extraction on the square-matched part of a Dulmage-Mendelsohn partition.

coupling

Coupling classification for candidate auxiliary blocks.

diagnostics

Diagnostics for the auxiliary-equality preprocessing pass (Phase 0).

dulmage_mendelsohn

Dulmage-Mendelsohn partition into under- / square- / overdetermined parts.

fbbt

Feasibility-Based Bound Tightening (FBBT).

incidence

Bipartite incidence graph between equality rows and variables.

inequality_projection

Inequality projection for InequalityCoupled candidate blocks.

licq

Phase 3 — LICQ degeneracy detection.

linear_eq_elim

Phase 6 — the TNLP wrapper that applies a EliminationPlan (issue #487).

linear_eq_plan

Phase 6, planning half — decide which variables a model’s linear equality rows determine (issue #487).

matching

Hopcroft-Karp bipartite matching on an crate::incidence::EqualityIncidence.

options

Option-table integration for pounce-presolve.

reduction_frame

Postsolve frame stack for the auxiliary-equality preprocessing pass.

redundant

Phase 2 — redundant linear-constraint detection.

trivial_elim

Trivial-elimination pre-pass for the auxiliary-equality preprocessing pipeline.

warm

Warm-start-aware presolve, retain the transformation, map warm points.

Structs

CachedBounds

PresolveTnlp

TNLP wrapper that re-presents the inner problem after presolve.

Enums

PresolveError

Errors that can arise while building a presolved TNLP.

WitnessRule

Which accepting test the witness-refutation gate uses to decide that a sampled point satisfies a row.

Functions

register

Re-export for callers that already imported pounce_presolve::register_options directly.

wrap_from_options

Convenience: read the presolve_* keys out of an OptionsList and call wrap_with_presolve.

wrap_with_presolve

Top-level entry: returns a TNLP wrapping inner with whatever presolve passes the option table has enabled. When the master switch is off, returns inner unchanged.

wrap_with_presolve_provider

Same as wrap_with_presolve but also installs an ExpressionProvider so passes like FBBT (issue #62) can see constraint expression trees. Callers who have the concrete inner TNLP type (pounce-cli with NlTnlp) should prefer this; the plain wrap_with_presolve leaves presolve_fbbt as a silent no-op.