layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # π Network Optimization ### Theory, Algorithms & EDA Applications @luk036 π¨βπ» Β· 2026 π --- ### π Agenda .pull-left[ **π§ Part 1: Theory** - Networks & Shortest Path - Negative Cycle Finding (NCF) - Flow & Potential Duality **π’ Part 2: Algorithms** - Feasibility Problems - Parametric Problems - Min-Cost Flow (linear β convex β constrained) ] .pull-right[ **π Part 3: MCF in EDA** - Base Model & Graph Definition - Practical EDA Constraints (9 types) - Continuous vs Discrete MCF - Specialized Models & Pipeline **π οΈ Part 4: Tools & Resources** - digraphx & C++ Ecosystem - Key Takeaways Β· All Resources ] --- class: nord-light, middle, center ## Part 1: Theory π§ --- ### π Networks Are Everywhere .pull-left[ **Where networks appear** - **VLSI** π β Circuit routing, timing - **Internet** π β Routing, traffic engineering - **Social Networks** π₯ β Influence, communities - **Transportation** π β GPS, airlines - **EDA** π β Placement, routing, PDN - **Biology** 𧬠β Metabolic pathways ] .pull-right[ .mermaid[ <pre> graph TD subgraph Networks["Network Types"] A1["VLSI"] --- A2["Internet"] A2 --- A3["Social"] A3 --- A4["Neural"] A4 --- A1 end B["Network\nOptimization"] --> Networks style B fill:#e74c3c,color:#fff style A1 fill:#4caf50 style A2 fill:#2196f3 style A3 fill:#ff9800 style A4 fill:#9c27b0 </pre> ] ] π [quickstart.html](quickstart.html) Β· [intro.md](intro.md) Β· [mindmap.md](mindmap.md) --- ### π£οΈ Shortest Path Problem $$ \min_{P \in \mathcal{P}_{st}} \sum_{e \in P} w(e) $$ **Bellman-Ford Algorithm**: $O(V \cdot E)$, handles negative weights, detects negative cycles. $$ \text{dist}[v] = \min(\text{dist}[v],\; \text{dist}[u] + w(u,v)) $$ .mermaid[ <pre> graph LR A[("s")] -->|"3"| B[("a")] A -->|"5"| C[("b")] B -->|"2"| D[("c")] C -->|"1"| D D -->|"4"| E[("t")] B -->|"-1"| E </pre> ] --- ### β Negative Cycle Finding (NCF) $$ \sum_{(i,j) \in C} w(i,j) < 0 $$ **NCF is the universal primitive** β powers Shortest Path, Feasibility, Cycle Canceling, Parametric Search, Convex MCF. .mermaid[ <pre> graph TD NCF["NCF Engine"] --> SP["Shortest Path"] NCF --> FEAS["Feasibility"] NCF --> OPT["Cycle Cancel"] NCF --> PARAM["Parametric"] NCF --> CVX["Convex MCF"] style NCF fill:#e74c3c,color:#fff style SP fill:#4caf50,color:#fff style FEAS fill:#2196f3,color:#fff style OPT fill:#ff9800,color:#fff style PARAM fill:#9c27b0,color:#fff style CVX fill:#f44336,color:#fff </pre> ] **Howard's algorithm** π: policy iteration, generator-based, no source needed. π [netflow+cvxopt.html](netflow+cvxopt.html) Β· [digraphx-remark.html](digraphx-remark.html) --- ### βοΈ Flow and Potential Duality .pull-left[ **Flow π§** $$ \text{div}\, {\color{green}x} = {\color{blue}A^\mathsf{T}} {\color{green}x} = 0 $$ - ${\color{green}x}$: edge flow - ${\color{blue}A}$: incidence matrix - **Cut** βοΈ: node bipartition ] .pull-right[ **Potential β‘** $$ {\color{blue}y} = {\color{green}A} {\color{firebrick}u} $$ - ${\color{firebrick}u}$: node potential - ${\color{blue}y}$: edge tension - **Cycle** π: closed path ] **Tellegen's Theorem**: ${\color{green}x}^\mathsf{T} {\color{blue}y} = 0$ β flow and tension are orthogonal. Foundation of complementary slackness. π [quickstart.html](quickstart.html) Β· [dec-remark.html](dec-remark.html) --- ### 𧩠From Combinatorial to Tractable **Key insight** π: Many **combinatorial** problems that seem inherently hard become **polynomial-time solvable** once formulated as network flow problems: .font-sm[ | Combinatorial Problem | Network Flow Formulation | Complexity | |------------------------|--------------------------|:---:| | **Shortest Path** π£οΈ | Feasible Potential Problem | **P** β | | **Max-Flow / Min-Cut** βοΈ | Special case of MCFP ($d = -[1,\dots,1]$) | **P** β | | **Bipartite Matching** π« | Max-Flow on bipartite graph | **P** β | | **Assignment Problem** π | Min-Cost Flow on bipartite graph | **P** β | | **Minimum Mean Cycle** π | Parametric Potential Problem | **P** β | | **Min-Cost Flow** π° | Linear Programming (Cycle Canceling) | **P** β | | **Min Cost-to-Time Ratio** π | Parametric Potential + NCF | **P** β | ] **Why?** The network structure (incidence matrix $A$, cycles, cuts) constrains the search space. NCF provides a **polynomial-time primitive** that elegantly handles all these problems. Once a problem is expressed in the language of **flow and potential**, it becomes tractable. π --- class: nord-light, middle, center ## Part 2: Algorithms π --- ### A. Feasibility Problems β .pull-left[ **Feasible Flow** $$\begin{array}{ll} {\color{green}c^-} \le {\color{green}x} \le {\color{green}c^+}, \\ {\color{blue}A^\mathsf{T}} {\color{green}x} = {\color{firebrick}b},\; {\color{firebrick}b}({\color{salmon}V}) = 0 \end{array}$$ **Theorem**: Feasible iff ${\color{firebrick}b}(S) \le {\color{green}c^+}(Q)$ for every cut $Q$. **Algorithm**: Painted network. ] .pull-right[ **Feasible Potential** $$\begin{array}{ll} {\color{blue}d^-} \le {\color{blue}y} \le {\color{blue}d^+}, \\ {\color{green}A} \cdot {\color{firebrick}u} = {\color{blue}y} \end{array}$$ **Theorem**: Feasible iff ${\color{blue}d^+}(P) \ge 0$ for every cycle $P$. **Algorithm**: Bellman-Ford. ] **Duality** β―: Flow (primal) β Potential (dual). Solving one solves the other. --- ### B. Parametric Problems π **Parametric Potential Problem** β for $z$ with concave $g(z)$, $d(z)$: $$\begin{array}{ll} \text{maximize} & {\color{purple}g}({\color{darkblack}z}), \\ \text{subject to} & {\color{blue}y} \le {\color{purple}d}({\color{darkblack}z}), \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y} \end{array}$$ **Linearity spectrum**: .font-sm[ | Type | $g(z), d(z)$ | Method | |------|--------------|--------| | **Linear** | Linear in $z$ | Binary search + NCF | | **Convex** | Concave, subgradients | Bisection / Ellipsoid + NCF | | **Quasi-convex** | $\Phi_\gamma$ convex family | Bisection + NCF | ] **Network insight**: For fixed $z$, feasibility β‘ NCF. Negative cycle $C$ iff $\sum_{(i,j) \in C} d_{ij}(z) < 0$. π [netflow+cvxopt.html](netflow+cvxopt.html) --- ### π Minimum Cycle Ratio (MCR) $$ \text{ratio}(C) = \frac{\sum c(e)}{\sum t(e)} $$ **Parametric reduction**: $w_r(e) = c(e) - r \cdot t(e)$ β negative cycle means $r$ too high. .mermaid[ <pre> graph LR R0["Guess r"] --> W["w_r(e) = c(e) - rΒ·t(e)"] W --> NCF{"Negative\nCycle?"} NCF -->|"Yes"| DEC["Decrease r"] NCF -->|"No"| INC["Increase r"] DEC --> W INC --> W </pre> ] Applications: clock period, slack maximization, yield-driven scheduling. --- ### C. Min-Cost Flow π° **Linear MCFP** β Cycle Canceling: $$\begin{array}{ll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x} \\ \text{s.t.} & 0 \le {\color{green}x} \le {\color{green}c}, \\ & {\color{blue}A^\mathsf{T}} {\color{green}x} = {\color{firebrick}b},\; {\color{firebrick}b}({\color{salmon}V}) = 0 \end{array}$$ **Descent**: $x_1 = x_0 + \alpha \cdot p$ with ${\color{blue}d}^\mathsf{T} p < 0$, ${\color{blue}A^\mathsf{T}} p = 0$ β **$p$ is a cycle**! .mermaid[ <pre> graph LR X0["Initial x"] -->|"Negative cycle p"| NCF["NCF"] NCF -->|"found"| UPDATE["x += Ξ±Β·p"] UPDATE --> NCF NCF -->|"none"| OPTIMAL["Optimal β "] </pre> ] π [netflow+cvxopt.html](netflow+cvxopt.html) Β· [Presentation_ Min-Cost Flow.md](Presentation_%20Min-Cost%20Flow%20%28MCF%29%20Algorithms%20%26%20Constrained%20Formal%20Models%20in%20EDA.md) --- ### From Linear to Convex to Constrained **Algorithm hierarchy** (easy β hard): | Problem | Key Technique | |---------|---------------| | **Linear MCF** | Cycle canceling with NCF | | **Convex MCF** | Gradient $\nabla f(x)$ as edge costs, NCF + line search | | **Quasi-convex MCF** | Bisection + NCF with sublevel-set $\nabla \Phi_\gamma(x)$ | | **Constrained MCF** ($s^\mathsf{T} x \le \gamma$) | Barrier method, NCF centering with $\nabla f + \frac{1}{t} \nabla \phi$ | **The NCF engine scales**: From shortest paths to non-linear constrained problems β all with the same primitive! π --- class: nord-light, middle, center ## Part 3: MCF in EDA π --- ### π― MCF: The Unified Backbone of EDA **Min-Cost Flow** is the **unified mathematical backbone** of modern EDA β replacing greedy heuristics with global optimal optimization. **Core EDA Application Scenarios**: - **Global / Detailed Routing** β Congestion optimization & track allocation - **Steiner Tree Construction** β Multi-pin net minimal-wire routing - **PDN Power Grid** β IR-drop & electromigration (EM) mitigation - **Cell Placement** β Bipartite assignment for minimal wirelength - **Clock Tree Synthesis (CTS)** β Skew & power optimization - **Layer Assignment & Via Minimization** β DRC-compliant routing - **High-Level Synthesis (HLS)** β Resource scheduling & allocation π Full talk: [Presentation_ Min-Cost Flow.md](Presentation_%20Min-Cost%20Flow%20%28MCF%29%20Algorithms%20%26%20Constrained%20Formal%20Models%20in%20EDA.md) --- ### π Base Formal MCF Network Model **Graph Definition**: ${\color{#2E86AB}{G = (V, E)}}$ β directed flow graph. .mermaid[ <pre> graph TD subgraph Graph["Flow Graph G"] direction LR N1(("vβ")) -->|"f_e, w_e, c_e"| N2(("vβ")) N1 --> N3(("vβ")) N2 --> N4(("vβ")) N3 --> N4 end subgraph Params["Parameters"] direction TD P1["c_e: capacity"] P2["w_e: unit cost"] P3["b(v): supply/demand"] end style Graph fill:#e3f2fd style Params fill:#fff3e0 </pre> ] - **Node set $V$**: Routing grid points, pins, PDN vertices, placement sites - **Edge set $E$**: Wire segments, vias, power grid branches - Edge params: ${\color{#A23B72}{c_e}}$ (capacity), ${\color{#F18F01}{w_e}}$ (unit cost), ${\color{#C73E1D}{f_e}}$ (flow) - Node params: ${\color{#39A78E}{b(v)}}$ (supply/demand), $\sum_v b(v) = 0$ --- ### Standard MCF Formulation **Objective (Minimize Total Cost)**: $$ \min \quad {\color{#2E86AB}{\sum_{e \in E} w_e f_e}} $$ **Hard Constraints**: $$ \begin{array}{ll} {\color{#A23B72}{0 \le f_e \le c_e}}, & \forall e \in E \quad \text{(Capacity)} \\[4pt] {\color{#39A78E}{\sum_{\delta^+(v)} f_e - \sum_{\delta^-(v)} f_e = b(v)}}, & \forall v \in V \quad \text{(Flow Conservation)} \end{array} $$ **Key properties**: - Single-commodity MCF has **totally unimodular** constraint matrix β LP solution = integer! - Multi-commodity MCF couples commodities through shared capacities - The base model is idealized β **industrial EDA requires 9 additional constraint categories** --- ### 𧩠EDA Practical Extra Constraints The base model is idealized; **real EDA requires 9 categories**: .font-sm[ | # | Constraint | Purpose | |---|-----------|---------| | 1 | **Timing** β±οΈ | Max delay for critical nets: $\sum w_{e,k} f_{e,k} \le W_k^{\max}$ | | 2 | **Congestion Capping** π§ | Tighten capacity in congested bins | | 3 | **DRC Spacing** π | Noisy/sensitive net isolation: $f_{e,k_1} + f_{e,k_2} \le 1$ | | 4 | **Layer Assignment** π | Per-layer capacity + forbidden layers | | 5 | **Via Budget** π© | Per-net and global via upper bounds | | 6 | **Fixed Paths** π€οΈ | Preserve manual/pre-routed nets | | 7 | **PDN IR-Drop/EM** β‘ | Voltage drop + electromigration limits | | 8 | **Congestion Penalty** π | Quadratic soft constraint on congestion | | 9 | **Discrete Tracks** π² | Integer track assignment ($f_{e,k} \in \{0,1\}$) | ] --- ### βοΈ Continuous vs Discrete MCF **The most critical theoretical distinction for EDA**: .pull-left[ **Continuous MCF (LP)** - ${\color{#277DA1}{f_{e,k} \in \mathbb{R}_{\ge 0}}}$ - Pure LP, **polynomial-time** - Fractional track occupation - **Default** for full-chip routing - Single-commodity: integral solution (totally unimodular) ] .pull-right[ **Discrete MCF (ILP)** - ${\color{#E01E35}{f_{e,k} \in \{0,1\}}}$ - Integer LP, **NP-hard** - Exact physical track model - Only for **local** refinement - Intractable at full-chip scale ] | MCF Type | Math | Scenario | Solvable? | |----------|------|----------|-----------| | Continuous | LP (Convex) | Full-chip, PDN | β Fast | | Discrete | ILP (Non-convex) | Track assign, DRC | β Approx. | --- ### 𧱠Specialized EDA MCF Models **1. Single-Commodity: Steiner Tree** π² - One multi-pin net, $c_e \to \infty$ - LP solution = integer (totally unimodular) - ${\color{#22577A}{\min \sum w_e f_e,\quad \nabla\cdot f = b(v)}}$ **2. Multi-Commodity: Global Routing** πΊοΈ - Each net = independent commodity sharing edges - ${\color{#3A0CA3}{\min \sum_{k,e} w_{e,k} f_{e,k},\quad \sum_k f_{e,k} \le c_e}}$ - Industrial: fractional LP relaxation **3. Convex Continuous: PDN IR/EM** β‘ - Quadratic cost: ${\color{#001233}{\min \sum r_e f_e^2}}$ - Hard constraints: $r_e f_e \le \Delta V_{\max}$ - Solvable to global optimum via convex optimization --- ### βοΈ Industrial Solving Pipeline **Why not exact discrete MCF?** Full-chip EDA: $10^5-10^6$ edges/nets β integer MCF is NP-hard at scale. **Industry Standard Pipeline**: .mermaid[ <pre> graph LR A["1. Continuous LP\nRelaxation"] --> B["2. Lagrangian\nDecomposition"] B --> C["3. Greedy\nRounding"] C --> D["4. Local Integer\nRepair"] style A fill:#4caf50,color:#fff style B fill:#2196f3,color:#fff style C fill:#ff9800,color:#fff style D fill:#f44336,color:#fff </pre> ] 1. **Continuous LP** β global congestion & wirelength optimization 2. **Lagrangian Decomposition** β decouple multi-commodity constraints 3. **Greedy Rounding** β fractional β discrete track assignment 4. **Local Integer Repair** β fix DRC/congestion violations locally **Complexity**: Single: $O(E\sqrt{V}\log U)$ Β· Multi-continuous: polynomial Β· Multi-discrete: NP-hard --- class: nord-light, middle, center ## Part 4: Tools & Applications π οΈ --- ### π¦ The digraphx Package **Python + C++** for directed graph optimization: ```python from digraphx import NegCycleFinder, min_cycle_ratio graph = { 'A': [('B', -1), ('C', 4)], 'B': [('C', 2), ('D', 2)], 'C': [('D', -3)], 'D': [('A', 1)] } finder = NegCycleFinder(graph) for cycle in finder.howard(): print(f"Negative cycle: {cycle}") ratio, cycle = min_cycle_ratio(graph, get_cost=lambda e: e['cost'], get_time=lambda e: e['time']) ``` **Features**: β Howard's (C++ CSR backend) β Generator β Warm-start β Python + C++ π [digraphx-remark.html](digraphx-remark.html) Β· [digraphx.md](digraphx.md) --- ### β‘ C++ Ecosystem .mermaid[ <pre> graph LR P1["digraphx\nPython API"] --> P2["digraphx-cpp\nCSR NCF Engine"] P2 --> P3["netoptim-cpp\nNetwork Oracles"] P3 --> P4["ellalgo-cpp\nCutting-Plane"] P1 --> P5["networkx\nGeneral Graphs"] P2 --> P6["LEMON\nC++ Graph Lib"] style P1 fill:#2196f3,color:#fff style P2 fill:#ff9800,color:#fff style P3 fill:#e74c3c,color:#fff style P4 fill:#9c27b0,color:#fff style P5 fill:#4caf50,color:#fff style P6 fill:#f44336,color:#fff </pre> ] π [netoptim-remark.html](netoptim-remark.html) Β· [performance-tuning.html](performance-tuning.html) Β· [py-cpp-remark.html](py-cpp-remark.html) --- ### π Discrete Exterior Calculus (DEC) **DEC** extends network concepts to higher dimensions: .mermaid[ <pre> graph LR A[Continuous\nCalculus] --> B[DEC\nDiscrete Forms] B --> C[Simplicial\nMeshes] B --> D[Differential\nForms] C --> E[Applications\nPoisson, Flow, Elasticity] D --> E style A fill:#2196f3,color:#fff style B fill:#9c27b0,color:#fff style C fill:#ff9800,color:#fff style D fill:#4caf50,color:#fff style E fill:#f44336,color:#fff </pre> ] Core operators: $d$ (exterior derivative), $\star$ (Hodge star), $\wedge$ (wedge product). Applications: Poisson equations, mesh smoothing, fluid flow, elasticity, computer vision. π [dec-remark.html](dec-remark.html) Β· [dec.md](dec.md) --- ### Applications Summary .font-sm[ | Application | Problem Type | Method | |-------------|-------------|--------| | **Clock Skew** β° | Feasible Potential | NCF | | **Matrix Scaling** β¨ | Parametric Potential | NCF + Cutting-plane | | **Delay Padding** β³ | Constrained MCF | NCF + Barrier | | **Performance** π | MCR | Parametric NCF | | **Global Routing** πΊοΈ | Multi-commodity MCF | LP + Rounding | | **PDN Optimization** β‘ | Convex MCF | Gradient + NCF | | **Steiner Tree** π² | Single-commodity MCF | LP (integral) | | **Layer Assignment** π | Integer MCF | Relax + Round | ] --- ### π― Key Takeaways 1. **Network flow makes problems tractable** π β Matching, assignment, minimum mean cycle, min cost-to-time ratio: once formulated as network flow, they're in **P**. The network structure (cycles, cuts, duality) constrains search. 2. **NCF is universal** β β Powers feasibility, optimality, parametric search, convex MCF, quasi-convex bisection. One primitive, many problems. 3. **Algorithm hierarchy**: Feasibility β Parametric β Linear MCF β Convex MCF β Quasi-convex MCF β Constrained MCF. Same NCF scales across all. 4. **MCF is the EDA backbone** π β Global routing, Steiner trees, PDN, placement, CTS β all unified. Continuous LP for global, discrete ILP for local precision. 5. **Industrial pipeline**: LP Relaxation β Lagrangian Decomposition β Greedy Rounding β Local Integer Repair. --- count: false class: nord-dark, middle, center # π Q&A --- count: false class: nord-dark, middle, center # π Thank You ### References π - Bellman (1958) β Shortest Path - Ford & Fulkerson (1956) β Max Flow - Howard (1960) β Policy Iteration - Karp (1967) β Min Mean Cycle - Orlin & Rothblum (1985) β Optimal Matrix Scaling Slides built with Remark.js π | KaTeX | Mermaid | Nord Theme