Forward solvers

Protocol

Forward solver protocol for the inner QP.

class micropurc.forward.base.FlowResult(x, lam_eq=None, info=None)[source]

Bases: object

Result of a forward flow solve.

Variables:

  • x (numpy.ndarray) – Optimal link-flow vector, shape (L,).

  • lam_eq (numpy.ndarray | None) – Equality-constraint duals (node potentials), shape (V,). The active-set test reads its dual slack from these.

  • info (dict[str, Any]) – Solver diagnostics such as status, iteration count, and residuals; empty when the backend reports none.

Parameters:
x: ndarray
lam_eq: ndarray | None = None
info: dict[str, Any] = None
class micropurc.forward.base.ForwardSolver(*args, **kwargs)[source]

Bases: Protocol

Protocol for forward (inner QP) solvers.

Given link costs \(c\) and node imbalances \(b\), an implementation solves

\[\min_x \; c^{\top} x + F(x) \quad \text{s.t.} \quad A x = b, \; x \ge 0 ,\]

where \(F\) is the perturbation the backend implements. The in-tree backend takes \(F(x) = \tfrac12 x^{\top} \mathrm{diag}(\mathrm{scale}_m) x\), which is why scale_m is part of the protocol.

solve(c, b, warm=None)[source]

Solve for optimal flows.

Parameters:

  • c (ndarray) – Link cost vector, shape (L,).

  • b (ndarray) – Node imbalance vector, shape (V,).

  • warm (Any | None) – Optional warm-start data from a previous solve.

Returns:

FlowResult with optimal flows and duals.

Return type:

FlowResult

property scale_m: ndarray

Per-link perturbation scale (e.g., link length), shape (L,).

PIQP backend

PIQP-based forward solver for quadratic perturbation.

class micropurc.forward.piqp_solver.PIQPFlowSolver(network, scale_m, config=None)[source]

Bases: object

Forward solver using PIQP for the quadratic perturbation.

\[\min_x \; c^{\top} x + \tfrac12 x^{\top} \mathrm{diag}(\mathrm{scale}_m) x \quad \text{s.t.} \quad A x = b, \; x \ge 0 ,\]

with no upper bound on \(x\).

The sparsity structure is fixed at construction, and each solve() updates only \(c\) and \(b\), so one PIQP setup serves every trip. PIQP is compiled into the package’s native extension, so no separate PIQP installation is involved.

One instance carries one solver state, and solve() releases the GIL while that state is being written, so an instance serves one thread at a time. Give each thread its own solver, or use solve_batch(), which runs a solver per worker internally.

Parameters:
__init__(network, scale_m, config=None)[source]

Set up the PIQP problem for this network.

Parameters:

  • network (Network) – Network with sparse incidence A.

  • scale_m (ndarray) – Per-link perturbation weights, shape (L,).

  • config (SolverConfig | None) – Solver configuration; defaults used if omitted.

Raises:

ValueError – If scale_m length does not match the link count.

Return type:

None

property scale_m: ndarray

Per-link perturbation scale, shape (L,).

solve(c, b, warm=None)[source]

Solve the quadratic flow problem for one right-hand side.

Parameters:

  • c (ndarray) – Link cost vector, shape (L,).

  • b (ndarray) – Node imbalance vector, shape (V,).

  • warm (Any | None) – Unused; PIQP manages its own state across calls.

Returns:

The optimal flows, the equality duals, and the solver diagnostics (status, iteration count, residuals, duality gap).

Return type:

FlowResult

solve_batch(c, origins, dests, n_threads=-1)[source]

Solve many unit-demand OD flow problems in parallel.

Every OD shares the cost c and differs only in the node-imbalance right-hand side (-1 at the origin, +1 at the destination), which the native multi-threaded batch solver exploits. Both entry points run the same solver on the same problem, so each OD’s flows agree with solve() up to the two paths’ termination settings.

This path takes eps_abs, eps_duality_gap_abs, and max_iter from config and leaves the relative termination criteria at PIQP’s own defaults, so zeroing eps_rel in config leaves this path unaffected and only solve() tightens.

Parameters:

  • c (ndarray) – Shared link cost vector, shape (L,).

  • origins (ndarray) – Origin node indices, shape (U,).

  • dests (ndarray) – Destination node indices, shape (U,).

  • n_threads (int) – Worker threads; -1 uses all hardware threads.

Returns:

Tuple (flows, ok) with flows of shape (U, L) float64 and ok of shape (U,) bool (per-OD solver success).

Return type:

tuple[ndarray, ndarray]