Speed up direct solver handoff by dropping explicit zeros from the constraint matrix

[FBumann]

Intent placeholder — @FBumann to replace with your own words.

Note

The following was generated by AI (found while investigating #813).

Motivation

The direct solver handoff hands HiGHS a constraint matrix full of explicitly stored zeros. Models whose expressions broadcast against a dense coordinate (e.g. a bus × line incidence block) store one coefficient per coordinate pair, most of them zero. For the sparse_network(250) benchmark:

• model.matrices.A: 1,506,000 stored entries, 18,000 structural nonzeros → 98.8% explicit zeros.

highspy.Highs.addRows cost scales with stored nnz, so we spend the handoff describing zeros (and materialise them in the solver — the peak-memory column below). This is independent of the highspy version regression in #813 — it's pure wasted work on every version.

Proposal

Drop explicit zeros before the direct handoff. Minimal version in linopy/solvers.py (Highs._build_solver_model, ~L1668):

A = A.tocsr()
A.eliminate_zeros()
...
h.addRows(num_cons, lower, upper, A.nnz, A.indptr, A.indices, A.data)

Mathematically identical — a zero coefficient doesn't change the constraint.

Better still, consider eliminating zeros centrally in model.matrices.A (or when the coefficient array is assembled) so the LP/MPS writers and the other direct backends (gurobi, xpress, …) all benefit, not just HiGHS.

Impact

Measured with the repro in #813 (dev-scripts/highs-addrows-repro/, runnable via uv run). Timings via pytest-benchmark; peak memory via pytest-benchmem (memray). Effect of eliminate_zeros() on the addRows handoff:

highspy	explicit zeros (1.5M nnz)	eliminate_zeros() (18k nnz)	speedup
1.13.1	~13 ms	~1.6 ms	8×
1.15.0	~51 ms	~1.7 ms	30×

Peak memory for the handoff also drops (currently ~65 MiB, dominated by the ~1.5M redundant coefficients). As a side effect this makes linopy insensitive to the #813 highspy regression.

Notes / to check

• Confirm no backend relies on structural zeros being present.
• Decide the right layer (per-backend vs central in matrices).
• Add a regression benchmark on stored-vs-structural nnz.

[coroa]

I agree it makes sense to eliminate zeros as early as possible, except when you don't want to. Especially when you want to update your model over multiple iterations with the persistent solver stuff, you need to keep the structure stable and then you would want to be able to have some 0s in there explicitly which are not eliminated.

Maybe it would even make more sense to auto-mask zeros on the expression level early. Rather than eliminating them from the CSR matrix.

[FBumann]

@coroa I opened 2 PRs to show how hard such changes might be, but I admit that i dont fully grasp the potential issues with other things ( like the one you mentioned). I would see this as a tracking issue, which would be great to tackle faithfully

[coroa]

I saw the two PRs. I am fully with you that we don't want to transfer explicit 0.

Isn't sanitize_zeros, which we already have on the Constraint and CSRConstraint actually what we want? Wasn't this triggered anyway automatically previously?

@FabianHofmann I am only worried about structure changes when we drop zeros? You have a better overview here?