NLF: A Resistor-Network Framework and Linear-Time Solver for Convex Network-Flow Equilibria

Jul 16, 2026

NLF (Nonlinear Laplacian Flow) provides a unified framework and near-linear-time solver for convex network-flow equilibria. Congestion routing, minimum-delay communication routing, and maximum flow share a single stationarity equation: the nonlinear graph Laplacian B ρ(Bᵀ ϕ)=αd with a monotone edge law encoding the underlying physics. The method uses an inexact damped chord-Newton iteration with frozen global Laplacian linearization, inverted by a lazily refreshed near-linear Laplacian solver. Experiments show fast convergence on large SuiteSparse road-network graphs and strong speedups versus interior-point and matrix-free baselines; a multicommodity extension and exact combinatorial max-flow recovery are also supported. Benchmarks and code are provided.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages25

Reading Time1 h 3 min

Introduction

The observation: a unified nonlinear Laplacian

Contribution

NLF framework and solver approach

Performance evaluation and results

Extensions: multicommodity and maximum flow

arXiv :2607 .02041v1 [math .NA] 2 Jul 2026 NLF: A RESISTOR-NETWORK FRAMEWORK AND LINEAR-TIME SOLVER FOR CONVEX NETWORK-FLOW EQUILIBRIA ∗ OREN E. LIVNE† Abstract. We present NLF (Nonlinear Laplacian Flow), a unified framework and linear-timesolver for convex network-flow equilibria. Congestion (traffic) routing, minimum-delay communication routing, and maximum flow—each the stationarity of a convex, edge-separable energy—share one form: the nonlinear graph Laplacian B ρ(B⊤ ϕ) = αd, where a monotone edge law ρe encodes the physics (undirected graphs; directed variants are future work) . NLF solves it by an inexact damped chord-Newton iteration whose frozen global linearization—a weighted graph Laplacian—is inverted by a lazily refreshed near-linear Laplacian solver (engine-agnostic; default: approximate Cholesky, LAMG+ interchangeable) . The whole nonlinear solve costs 2–4 linear Laplacian solves, so a nearlinear inner solve makes the wall-clock empirically O (m) in the edge count m (not a proved bound) . On single-commodity congestion over real road-network topologies (BPR cost), NLF converges for all 2 ,003 SuiteSparse corpus graphs up to 1 .8 × 107 edges and on three larger graphs up to 5 .6 × 107 edges. Against a state-of-the-art interior-point method (IPM), NLF was a median 2 .6 × faster where both converge and > 45 × on the poorly-separable graphs where the IPM’s direct KKT core is superlinear; against matrix-free L-BFGS, a median 4 .2 × faster and the only solver to finish—within a 5 × wall-clock budget—on the 90 hardest instances. A multicommodity extension routes K commodities through one shared hierarchy at O (Km) per step; on real capacity data, congestion inflates sharedcorridor costs (up to 8 .8×) without rerouting. The same machinery recovers the exact combinatorial max-flow as a short sequence of Laplacian solves, with the cut potential as a by-product. Code and benchmarks: [https://github.com/orenlivne/nlf](https://github.com/orenlivne/nlf). Key words. network equilibrium, traffic assignment, maximum flow, algebraic multigrid, nonlinear multigrid, inexact Newton methods, continuation, graph Laplacian AMS subject classifications. 90B20, 90C35, 65F10, 65N55, 90B10, 05C21 1. Introduction. Flows on networks at equilibrium are everywhere: drivers distributing over a road map until no route is faster (traffic assignment [9, 10 , 11]), packets routed to minimize delay in a communication network [15, 16], current in a resistor network [26], and—at the combinatorial extreme—the maximum flow through a capacitated graph [17, 18 , 20] . These look like different problems with different algorithms: traffic assignment is solved by Frank–Wolfe or general convex optimization, max-flow by augmenting-path or push–relabel combinatorics. We make a unifying observation and build a single fast solver on it. The observation. Each of these is the stationary point of a convex, edge-separable energy in the node potentials, and its Euler equation is one and the same nonlinear graph Laplacian, (1 . 1) B ρ (B⊤ ϕ) = αd, where B is the node–edge incidence matrix, ϕ the node potentials, d a source/sink demand, α a load, and ρe a monotone edge law that alone encodes the physics: a saturating ρe gives a hard capacity (max flow); a gently rising ρe gives a congestion cost (traffic) 1 . The flow is fe = ρe 􀀀 (B⊤ ϕ)e 􀀁, and every Newton linearization of (1.1) isan ordinary weighted graph Laplacian J = B diag(ρ′)B ⊤ . For congestion and routing problems α is a given input; for maximum flow, α is an unknown to be maximized. ∗ Submitted to the editors July 3, 2026 . †Pine Birch Analytics, 35 Kelinger Rd, Churchville, PA 18966-1033 ([oren.livne@gmail.com](oren.livne@gmail.com), tel. 312-533-9130, [pinebirchanalytics.com](pinebirchanalytics.com); ORCID: 0000-0001-6700-483X). 1 Notation: ρ acts componentwise and ρe denotes the law on an individual edge e. 2 O. E. LIVNE To obtain a fast nonlinear solver, we use an inexact chor

FAQs

What is NLF and what problem class does it target?

NLF (Nonlinear Laplacian Flow) is a unified framework for computing convex network-flow equilibria. It targets congestion routing, minimum-delay routing, and maximum flow within a single nonlinear Laplacian stationarity form.

How does the paper unify traffic routing and maximum flow under one mathematical equation?

All three problems are cast as stationary points of a convex edge-separable energy with Euler equation B ρ(Bᵀ ϕ)=αd. The specific problem behavior is determined by the monotone edge law ρe, including whether it saturates.

How does the solver achieve near-linear performance in practice?

NLF uses an inexact damped chord-Newton iteration with frozen global linearization. Each linearization becomes a weighted graph Laplacian that is solved using a lazily refreshed near-linear Laplacian solver (e.g., approximate Cholesky or LAMG+), yielding an empirically O(m) cost in the number of edges for the nonlinear solve.

Jul 16, 2026

Upload by Olivia Brown