layout: true class: typo, typo-selection --- class: nord-dark, middle, center # Network Optimization: Quick Start ⚡ @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Fundamentals** 🧠 - Network Concepts - Flow & Potential **Part 2: Algorithms** 🔄 - Cycle Detection - Negative Cycle ] .pull-right[ **Part 3: Applications** 🔬 - Clock Skew - Delay Padding ] --- class: nord-light, middle, center ## 🎬 Introduction --- ### Why and why not ❓ .pull-left[ Why? ✔️ - 👍 Algorithms are available for common network problems (Python: `networkx`, `digraphx`, C++: Boost Graph Library (BGL)): - Explore the locality of network. - 👍 Be able to solve discrete problems optimally (e.g. matching/assignment problems) - 👍 Bonus: gives you insight into the most critical parts of the network (critical cut/cycle) ] .pull-right[ Why not? ✖️ - 👎 The theory is hard to understand. - 👎 Algorithms are hard to understand (some algorithms do not allow users to have an input flow in reverse directions, but create edges internally for the reverse flows). - 👎 There are too many algorithms available. You have to choose them wisely. ] --- ### Flow and Potential ⚖️ .pull-left[ - Cut ✂️ - Current ⚡ - Flow ${\color{green}x}$ 💧 - Sum of ${\color{green}x}_{ij}$ around a node = 0 🔄  ] .pull-right[ - Cycle/Path 🔄 - Voltage 🔋 - Tension ${\color{blue}y}$ 🏗️ - Sum of ${\color{blue}y}_{ij}$ around a cycle = 0 🔄  ] --- ### If you don't know more... 🤔 - For the min-cost linear flow problem, the best guess is to use the "network simplex algorithm". - For the min-cost linear potential problem: formulate it as a dual (flow) problem. 🔄 - For the parametric potential problem (single parameter), the best guess is to use Howard's algorithm. ⏱️ - All these algorithms are based on the idea of finding "negative cycle". ➖ - You can apply the same principle to the nonlinear problems. 🔄 --- ### For dual problems... 🔄 - Dual problems can be solved by applying the same principle. 🔄 - Finding negative cycles is replaced by finding a negative "cuts", which is more difficult... ✂️ - ...unless your network is a planar graph. --- ### Guidelines for the average users 👨💻 - Look for specialized algorithms for specialized problems. For example, for bipartite maximum cardinality matching, use the Hopcroft-Karp matching algorithm. 🤝 - Avoid creating edges with infinite costs. Delete them or reformulate your problem. ♾️ --- ### Guidelines for algorithm developers 👩💻 - Make "negative cycles" as orthogonal to each other as possible. ➖ - Reuse previous solutions as a new starting point for finding negative cycles. 🔄 --- class: nord-light, middle, center ## 💡 Essential Concepts --- ### Basic elements of a network 🌐 - Definition (network) A *network* is a collection of finite-dimensional vector spaces, which includes *nodes* and *edges*/*arcs*: - ${\color{salmon}V} = \{ {\color{brown}v_1}, {\color{brown}v_2}, \cdots, {\color{brown}v_N} \}$, where $|{\color{salmon}V}| = N$ - ${\color{lime}E} = \{ {\color{darkgreen}e_1}, {\color{darkgreen}e_2}, {\color{darkgreen}e_3}, \cdots, {\color{darkgreen}e_M} \}$, where $|{\color{lime}E}| = M$ which satisfies 2 requirements: 1. The boundary of each edge is comprised of the union of nodes 2. The intersection of any edges is either empty or the boundary node of both edges. --- ### Network 🌐 - By this definition, a network can contain self-loops and multi-edges. 🔄 - A *graph* structure encodes the neighborhood information of nodes and edges. - Note that Python's NetworkX requires special handling of multi-edges. 🐍 - The most efficient graph representation is an adjacency list. 📝 - The concept of a graph can be generalized to *complex*: node, edge, face... 🧩 #### Types of graphs Bipartite graphs, trees, planar graphs, st-graphs, complete graphs. --- ### Orientation 🧭 .pull-left[ An *orientation* of an edge is an ordering of its boundary node $(s, t)$, where - $s$ is called a source/initial node - $t$ is called a target/terminal node 👉 Note: orientation != direction #### Coherent Two orientations to be the same is called *coherent* ] .pull-right[  ] --- ### Node-edge Incidence Matrix - Definition (Incidence Matrix) An $N \times M$ matrix ${\color{blue} A^\mathsf{T} }$ is a node-edge incidence matrix with entries: $${\color{green} A}(i,j) = \begin{cases} +1 & \text{if ${\color{darkgreen}e_i}$ is coherent with the orientation of node ${\color{brown}v_j}$,} \\ -1 & \text{if ${\color{darkgreen}e_i}$ is not coherent with the orientation of node ${\color{brown}v_j}$,} \\ 0 & \text{otherwise.} \end{cases} $$ - Example $${\color{blue} A^\mathsf{T} } = \begin{bmatrix} 0 & -1 & 1 & 1 & 0 \\ 1 & 1 & 0 & -1 & -1 \\ -1 & 0 & -1 & 0 & 1 \end{bmatrix}$$ --- ### Chain ⛓️ - Definition (Chain $\tau$) An edge/node *chain* $\tau$ is an $M$/$N$-tuple of scalar that assigns a coefficient to each edge/node,where $M$/$N$ is the number of distinct edges/nodes in the network. - Remark (II) A chain may be viewed as an (oriented) indicator vector representing a set of edges/nodes. - Example (II) $[0, 0, 1, 1, 1]$, $[0, 0, 1, -1, 1]$ --- ### Discrete Boundary Operator ✂️ - Definition (Boundary operator) The *boundary* operator ${\color{blue}\partial} = {\color{blue}A^\mathsf{T} }$. - Definition (Cycle) A chain is said to be a *cycle* if it is in the null-space of the boundary operator, i.e. ${\color{blue}A^\mathsf{T} } \tau = 0$. - Definition (Boundary) A chain $\beta$ is said to be a *boundary* of $\tau$ if it is in the range of the boundary operator. --- ### Co-boundary Operator ${\color{green}\mathrm{d} }$ 🔄 - Definition (Co-boundary operator) The *co-boundary* (or *differential*) operator ${\color{green}\mathrm{d} } = {\color{blue}\partial}^* = ({\color{blue}A^\mathsf{T} })^* = {\color{green}A}$ - 👉 Note Null-space of ${\color{green}A}$ is \#components of a graph --- ### Discrete Stokes' Theorem 📜 - Let $${\color{green}\tau_i} = \begin{cases} 1 & \mathrm{if}\ {\color{darkgreen}e_i} \in {\color{lime} S}, \\ 0 & \mathrm{otherwise.} \end{cases}$$ - Conventional (integration): $${\color{purple}\int}_{\color{lime}S} {\color{green}\mathrm d} \tilde{\color{firebrick}\omega} = {\color{purple}\oint}_{\color{blue}\partial \color{lime}S} \tilde{\color{firebrick}\omega}$$ - Discrete (pairing): $${\color{purple}{[} \color{green}\tau}, {\color{green}A}{\color{firebrick}\omega}{\color{purple}]} = {\color{purple}[ \color{blue}A^\mathsf{T} \color{green}\tau}, {\color{firebrick}\omega}{\color{purple}]}$$ --- ### Fundamental Theorem of Calculus - Conventional (integration): $\int_a^b f(t) dt = F(b) - F(a)$ - Discrete (pairing): $[{\color{green}\tau_1}, {\color{green} A} {\color{firebrick}c^0}] = [{\color{blue} A^\mathsf{T} }{\color{green}\tau_1}, {\color{firebrick}c^0}]$  --- ### Divergence and Flow 💧 - Definition (Divergence) $\text{div}\, {\color{green}x} = {\color{blue} A^\mathsf{T} } {\color{green}x}$ - Definition (Flow) ${\color{green}x}$ is called a *flow* if $\sum \text{div}\, {\color{green}x} = 0$, where all negative entries of (div ${\color{green}x}$) are called *sources* and positive entries are called *sinks*. - Definition (Circulation) A network is called a *circulation* if there is no source or sink. In other words, $\text{div}\, {\color{green}x} = 0$ --- ### Tension and Potential ⚡ - Definition (Tension) A tension (in co-domain) ${\color{blue}y}$ is a *differential* of a *potential* ${\color{firebrick}u}$, i.e. ${\color{blue}y}= {\color{green} A} {\color{firebrick}u}$. - Theorem (Tellgen's) Flow and tension are bi-orthogonal (isomorphic). - Proof $0 = [{\color{blue} A^\mathsf{T} } {\color{green}x}, {\color{firebrick}u}] = ({\color{blue} A^\mathsf{T} } {\color{green}x})^\mathsf{T} {\color{firebrick}u} = {\color{green}x}^\mathsf{T} ({\color{green} A} {\color{firebrick}u}) = {\color{green}x}^\mathsf{T} {\color{blue}y}$ --- ### Path 🛣️ A path indicator vector ${\color{green}\tau}$ of ${\color{lime}P}$ that $${\color{green}\tau_i} = \begin{cases} 1 & \mathrm{if}\ {\color{darkgreen}e_i} \in {\color{lime}P}, \\ 0 & \mathrm{otherwise.} \end{cases}$$ - Theorem [total tension ${\color{blue}y}$ on ${\color{lime}P}$] = [total potential on the boundary of ${\color{lime}P}$]. - Proof ${\color{blue}y}^\mathsf{T} {\color{green}\tau} = ({\color{green} A} {\color{firebrick}u})^\mathsf{T} {\color{green}\tau} = {\color{firebrick}u}^\mathsf{T}({\color{blue} A^\mathsf{T} } {\color{green}\tau}) = {\color{firebrick}u}^\mathsf{T}({\color{blue} \partial} {\color{lime}P})$. --- ### Cut ✂️ Two node sets ${\color{salmon}S}$ and ${\color{salmon}S}'$ (the complement of ${\color{salmon}S}$, i.e. ${\color{salmon}V} - {\color{salmon}S}$). A cut ${\color{steelblue}Q}$ is an edge set, denoted by $[{\color{salmon}S}, {\color{salmon}S}']^-$. A cut indicator vector ${\color{blue}q}$ (oriented) of ${\color{steelblue}Q}$ is defined as ${\color{green} A} {\color{firebrick}c}$ where $${\color{firebrick}c_i} = \begin{cases} 1 & \text{if } {\color{brown}v_i} \in {\color{salmon}S} \,, \\ 0 & \text{otherwise}\,. \end{cases} $$ - Theorem (Stokes' theorem!) [Total divergence of ${\color{green}x}$ on ${\color{lime}S}$] = [total ${\color{green}x}$ across ${\color{steelblue}Q}$]. - Proof $(\text{div}\,{\color{green}x})^\mathsf{T} {\color{firebrick}c} = ({\color{blue} A^\mathsf{T} } {\color{green}x})^\mathsf{T} {\color{firebrick}c} = {\color{green}x}^\mathsf{T} ({\color{green} A} {\color{firebrick}c}) = {\color{green}x}^\mathsf{T} {\color{blue}q}$. --- ### Examples  --- class: nord-light, middle, center ## Feasibility Problems ✅ --- --- ### Feasible Flow/Potential Problem ⚖️ .pull-left[ Feasible Flow Problem 💧 - Find a flow ${\color{green}x}$ such that: $$\begin{array}{ll} {\color{green}c^-} \leq {\color{green}x} \leq {\color{green}c^+}, \\ {\color{blue} A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, {\color{firebrick}b}({\color{salmon}V}) = 0. \end{array}$$ - Can be solved using: - Painted network algorithm - If no feasible solution, return a "negative cut". ✂️ ] .pull-right[ Feasible Potential Problem: ⚡ - Find a potential ${\color{firebrick}u}$ such that: $$\begin{array}{ll} {\color{blue}d^-} \leq {\color{blue}y} \leq {\color{blue}d^+} \\ {\color{green}A} \cdot {\color{firebrick}u} = {\color{blue}y}. \end{array}$$ - Can be solved using: - Bellman-Ford algorithm - If no feasible solution, return a "negative cycle". ➖ ] --- ### Examples .pull-left[ Genome-scale reaction (primal) 🧬 - ${\color{green} A}$: Stoichiometric matrix - ${\color{green}x}$: reactions between metabolites/proteins - ${\color{green}c^-} \leq {\color{green}x} \leq {\color{green}c^+}$: constraints on reaction rates ] .pull-right[ Timing constraints (co-domain) ⏱️ - ${\color{blue} A^\mathsf{T} }$: incidence matrix of timing constraint graph - ${\color{firebrick}u}$: arrival time of clock - ${\color{blue}y}$: clock skew - ${\color{blue}d^-} \leq {\color{blue}y} \leq {\color{blue}d^+}$: setup- and hold-time constraints ] --- ### Feasibility Flow Problem 💧 - Theorem (feasibility flow) The problem has a feasible solution if and only if ${\color{firebrick}b}({\color{salmon}S}) \leq {\color{green}c^+}({\color{steelblue}Q})$ for all cuts ${\color{steelblue}Q} = [{\color{salmon}S},{\color{salmon}S}']$ where ${\color{green}c^+}({\color{steelblue}Q})$ = upper capacity [1, p. 56]. --- ### Proof (if-part) ✅ Let ${\color{blue}q} = {\color{green} A} \cdot {\color{firebrick}k}$ be a cut vector (oriented) of ${\color{steelblue}Q}$. Then - ${\color{green}c^-} \leq {\color{green}x} \leq {\color{green}c^+}$ -- - ${\color{blue}q}^\mathsf{T} {\color{green}x} \leq {\color{green}c^+}({\color{steelblue}Q})$ -- - $({\color{green} A} \cdot {\color{firebrick}k})^\mathsf{T} {\color{green}x} \leq {\color{green}c^+}({\color{steelblue}Q})$ -- - ${\color{firebrick}k}^\mathsf{T} {\color{blue} A^\mathsf{T} } {\color{green}x} \leq {\color{green}c^+}({\color{steelblue}Q})$ -- - ${\color{firebrick}k}^\mathsf{T} {\color{firebrick}b} \leq {\color{green}c^+}({\color{steelblue}Q})$ -- - ${\color{firebrick}b}({\color{salmon}S}) \leq {\color{green}c^+}({\color{steelblue}Q})$ --- ### Feasibility Potential Problem ⚡ - Theorem (feasibility potential) The problem has a feasible solution if and only if ${\color{blue}d^+}({\color{lime}P}) \geq 0$ for all cycles ${\color{lime}P}$ where ${\color{blue}d^+}({\color{lime}P})$ = upper span [1, p. ??]. --- ### Proof (if-part) ✅ Let ${\color{green}\tau}$ be a path indicator vector (oriented) of ${\color{lime}P}$. Then - ${\color{blue}d^-} \leq {\color{blue}y} \leq {\color{blue}d^+}$ -- - ${\color{green}\tau}^\mathsf{T} {\color{blue}y} \leq {\color{blue}d^+}({\color{lime}P})$ -- - ${\color{green}\tau}^\mathsf{T} ({\color{green} A} \cdot {\color{firebrick}u}) \leq {\color{blue}d^+}({\color{lime}P})$ -- - $({\color{blue} A^\mathsf{T} } {\color{green}\tau})^\mathsf{T} {\color{firebrick}u} \leq {\color{blue}d^+}({\color{lime}P})$ -- - $({\color{blue} \partial} {\color{lime}P})^\mathsf{T} {\color{firebrick}u} \leq {\color{blue}d^+}({\color{lime}P})$ -- - $0 \leq {\color{blue}d^+}({\color{lime}P})$ --- ### Remarks - The only-if part of the proof is constructive. It can be done by constructing an algorithm to obtain the feasible solution. - ${\color{blue}d^+}$ could be $\infty$ or zero, etc. ♾️ - ${\color{blue}d^-}$ could be $-\infty$ or zero, etc. ♾️ - ${\color{green}c^+}$ could be $\infty$ or zero, etc. ♾️ - ${\color{green}c^-}$ could be $-\infty$ or zero, etc. ♾️ **Note**: most tools require that ${\color{green}c^-}$ must be zero such that the solution flow ${\color{green}x}$ is always positive. --- ### Convert to the elementary problem 🔄 .pull-left[ - By splitting every edge into two, the feasibility flow problem can reduce to an elementary one: - Find a flow ${\color{green}x}$ such that $$\begin{array}{ll} {\color{green}c} \leq {\color{green}x}, \\ {\color{blue}A_1^\mathsf{T} } {\color{green}x} = {\color{firebrick}b_1}, \\ {\color{firebrick}b_1}({\color{salmon}V_1}) = 0. \end{array}$$ ] .pull-right[ Original: .mermaid[ <pre> graph LR A(("i")) -- "[c-, c+]" --> B(("j")) </pre> ] Modified: .mermaid[ <pre> graph LR A(("i")) -- "c-" --> B(("k")) B -. "- c+" .-> C(("j")) B:::Rose classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236 </pre> ] ] --- ### Convert to the elementary problem 🔄 .pull-left[ - By adding a reverse edge for every edge, the feasibility potential problem can reduce to an elementary one: - Find a potential ${\color{firebrick}u}$ such that $$\begin{array}{ll} {\color{blue}y_2} \leq {\color{blue}d}, \\ {\color{green}A_2} {\color{firebrick}u} = {\color{blue}y_2} \end{array}$$ where ${\color{green}A_2}$ is the incident matrix of the modified network. ] .pull-right[ Original: .mermaid[ <pre> graph LR A(("i")) -- "[d-, d+]" --> B(("j")) </pre> ] Modified: .mermaid[ <pre> graph LR A(("i")) -- "d+" --> B(("j")) A -. "- d-" .-> B(("j")) </pre> ] ] --- ### Basic Bellman-Ford Algorithm ⏱️ .font-sm.mb-xs[ ```matlab function BellmanFord(list vertices, list edges, vertex source) // Step 1: initialize graph for each vertex i in vertices: if i is source then u[i] := 0 else u[i] := inf predecessor[i] := null // Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge (i, j) with weight d in edges: if u[j] > u[i] + d[i,j]: u[j] := u[i] + d[i,j] predecessor[j] := i // Step 3: check for negative-weight cycles for each edge (i, j) with weight d in edges: if u[j] > u[i] + d[i,j]: error "Graph contains a negative-weight cycle" return u[], predecessor[] ``` ] --- .font-sm.mb-xs[ ```python def _neg_cycle_relaxation(G, pred, dist, source, weight): G_succ = G.succ if G.is_directed() else G.adj inf = float('inf') n = len(G) count = {} q = deque(source) in_q = set(source) while q: u = q.popleft() in_q.remove(u) if pred[u] not in in_q: dist_u = dist[u] for v, e in G_succ[u].items(): dist_v = dist_u + get_weight(e) if dist_v < dist.get(v, inf): if v not in in_q: q.append(v) in_q.add(v) count_v = count.get(v, 0) + 1 if count_v == n: return v count[v] = count_v dist[v] = dist_v pred[v] = u return None ``` ] --- ### Example 1 : Clock skew scheduling ⏰ - Goal: intentionally assign an arrival time $u_i$ to each register so that the setup and hold time constraints are satisfied. - Note: the clock skew ${\color{blue}s}_{ij} = {\color{firebrick}u_i} - {\color{firebrick}u_j}$ is more important than the arrival time ${\color{firebrick}u}$ itself, because the clock runs periodically. - In the early stages, fixing the timing violation could be done as soon as a negative cycle is detected. A complete timing analysis is unnecessary at this stage. --- ### Example 2 : Delay padding + clock skew scheduling ⏰ - Goal: intentionally "insert" a delay $p$ so that the setup and hold time constraints are satisfied. - Note that a delay can be "inserted" by swapping a fast transistor into a slower transistor. - Traditional problem formulation: Find $p$ and ${\color{firebrick}u}$ such that $$\begin{array}{ll} {\color{blue}y} \leq {\color{blue}d} + p, \\ {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, p \geq 0 \end{array}$$ - Note 1: Inserting delays into some local paths may not be allowed. - Note 2: The problem can be reduced to the standard form by modifying the network (timing constraint graph) --- ### Four possible ways to insert delay ⏳ .pull-left[ No delay:  $p_s = p_h$:  ] .pull-right[ Independent:  $p_s \geq p_h$:  ] --- ### Example .pull-left[ Original: .mermaid[ <pre> graph LR A(("v1")) -- "TCP - 3" --> B(("v2")) A -. "2" .-> B B -- "TCP - 7" --> A B -. "4" .-> A </pre> ] ] .pull-right[ Modified: .mermaid[ <pre> graph LR A(("v1")) -- "TCP - 3" --> C("v3") A -. "2" .-> C C -. "0" .-> B(("v2")) B -- "TCP - 7" --> A B -. "4" .-> A </pre> ] ] --- ### DiGraphX Example ```python TCP: float = 6.5 digraph: Dict[str, Dict[str, float]] = { "v1": {"v2": TCP - 7, "v3": 2}, "v2": {"v1": 4, "v3": 0}, "v3": {"v1": TCP - 3}, } dist: Dict[str, float] = {"v1": 0, "v2": 0, "v3": 0} beta, num_iter, _ = even(digraph, 10, dist) assert num_iter < 10 assert beta == approx(1.0) assert dist == {"v1": -27.0, "v2": -28.5, "v3": -29.5} # v1: 2.5, v2: 1.0, v3: 0.0 ``` --- ### Remarks (III) - If there exists a negative cycle, it means that timing cannot be fixed using simply this technique. - Additional constraints, such as $p_s \leq p_{\max}$, can be imposed. --- class: nord-light, middle, center ## Parametric Problems 📈 --- ### Parametric Potential Problem (PPP) - Consider a parameter potential problem: $$\begin{array}{ll} \text{maximize} & {\color{coral}\beta} \\ \text{subject to} & {\color{blue}y} \leq {\color{olive}d}({\color{coral}\beta}), \\ & {\color{green}A} \cdot {\color{firebrick}u} = {\color{blue}y} \end{array}$$ where ${\color{olive}d}({\color{coral}\beta})$ is a *monotonic decreasing* function. - If ${\color{olive}d}({\color{coral}\beta})$ is a linear function $(m - s {\color{coral}\beta})$ where $s$ is non-negative, the problem reduces to the well-known *minimum cost-to-time ratio problem*. - If $s$ = constant, it further reduces to the *minimum mean cycle problem*. **Note:** Parametric flow problem can be defined similarly. --- ### Examples (III) - ${\color{olive}d}({\color{coral}\beta})$ is linear $(m - s {\color{coral}\beta})$: - Optimal clock period scheduling problem ⏰ - Slack maximization problem ⏳ - Yield-driven clock skew scheduling ⏰ (Gaussian) - ${\color{olive}d}({\color{coral}\beta})$ is non-linear: - Yield-driven clock skew scheduling ⏰ (non-Gaussian) - Multi-domain clock skew scheduling ⏰ --- ### Examples (IV) - Lawler's algorithm (binary search based) 🔍 - Howard's algorithm (cycle cancellation) ➖ - Young's algorithm (path based) 🛣️ - Burns' algorithm (path based) 🛣️ - for clock period optimization problem (all elements of $s$ are either 0 or 1) - Several hybrid methods have also been proposed --- ### Remarks (IV) - Need to solve feasibility problems many times. 🔄 - Data structures, such as Fibonacci heap or spanning tree/forest, can be used to improve efficiency 🌳 - For multi-parameter problems, the *ellipsoid method* can be used. 🏈 - Example 1: yield-driven clock skew scheduling ⏰ (c.f. lecture 5) --- ### Example 2: yield-driven delay padding ⏳ - The problem can be reduced to the standard form by modifying the underlying constraint graph. --- ### Four possible way to insert delay ⏳ .pull-left[ No delay:  $p_s = p_h$:  ] .pull-right[ Independent:  $p_s \geq p_h$:  ] --- class: nord-light, middle, center ## Min-cost Flow/Potenial Problem 💰 --- ### Elementary Optimal Problems 💯 - Elementary Flow Problem: $$\begin{array}{ll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x} + p \\ \text{s. t.} & {\color{green}c} \leq {\color{green}x}, \\ & {\color{blue} A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - Elementary Potential Problem: $$\begin{array}{ll} \text{max} & {\color{firebrick}b}^\mathsf{T} {\color{firebrick}u} - ({\color{green}c}^\mathsf{T} {\color{blue}y} + q) \\ \text{s. t.} & {\color{blue}y} \leq {\color{blue}d}, \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y} \end{array}$$ --- ### Elementary Optimal Problems (Cont'd) 🔄 - The problems are dual to each other if $p + q = -{\color{green}c}^\mathsf{T} {\color{blue}d}, ({\color{green}x} - {\color{green}c})^\mathsf{T}({\color{blue}d} - {\color{blue}y}) = 0, {\color{green}c} \leq {\color{green}x}, {\color{blue}y} \leq {\color{blue}d}$ - Since ${\color{firebrick}b}^\mathsf{T} {\color{firebrick}u}$ = $({\color{blue} A^\mathsf{T} } {\color{green}x})^\mathsf{T} {\color{firebrick}u} = {\color{green}x}^\mathsf{T} {\color{green}A} {\color{firebrick}u} = {\color{green}x}^\mathsf{T} {\color{blue}y},$ $[\min]-[\max] = ({\color{blue}d}^\mathsf{T} {\color{green}x} + p) - ({\color{firebrick}b}^\mathsf{T} {\color{firebrick}u} - [{\color{green}c}^\mathsf{T} {\color{blue}y} + q])$ = ${\color{blue}d}^\mathsf{T} {\color{green}x} + {\color{green}c}^\mathsf{T} {\color{blue}y} - {\color{green}x}^\mathsf{T} {\color{blue}y} + p + q = ({\color{green}x} - {\color{green}c})^\mathsf{T} ({\color{blue}d} - {\color{blue}y}) \geq 0$ - $[\min] - [\max]$ when equality holds. --- ### Remark (V) - We can formulate a linear problem in primal or dual form, depending on which solution method is more appropriate: - Incremental improvement of feasible solutions - Design variables are in the integral domain: - The max-flow problem (i.e. ${\color{blue}d}^\mathsf{T} = [-1, -1, \cdots, -1]^\mathsf{T}$) may be better solved by the dual method. --- ### Linear Optimal Problems - Optimal Flow Problem: $$\begin{array}{ll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x} + p \\ \text{s. t.} & {\color{green}c^-} \leq {\color{green}x} \leq {\color{green}c^+}, \\ & {\color{blue} A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - Optimal Potential Problem: $$\begin{array}{ll} \text{max} & {\color{firebrick}b}^\mathsf{T} {\color{firebrick}u} - ({\color{green}c}^\mathsf{T} {\color{blue}y} + q) \\ \text{s. t.} & {\color{blue}d^-} \leq {\color{blue}y} \leq {\color{blue}d^+}, \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y} \end{array}$$ --- ### Linear Optimal Problems (II) By modifying the network: - The problem can be reduced to the elementary case [pp.275-276] piece of cake 🍰 - Piece-wise linear convex cost can be reduced to this linear problem [p.239,p.260] The problem has been extensively studied and has numerous applications. --- ### Remark (VI) - We can transform the cost function to be non-negative by reversing the orientation of the negative cost edges. - Then reduce the problem to the elementary case (or should we???) --- ### Algorithms for Optimal Flow Problems 💧 - Successive shortest path algorithm 🛣️ - Cycle cancellation method ➖ - Iteratively insert additional minimal flows according to a negative cycle of the residual network until no negative cycles are found. - Scaling method ⚖️ --- ### For Special Cases ⭐ - Max-flow problem (${\color{blue}d} = -[1, \cdots, 1]$) - Ford-Fulkerson algorithm: iteratively insert additional minimal flows according to an augmented path of the residual network, until no augmented paths of the residual network are found. - Pre-flow Push-Relabel algorithm (dual method???) - Matching problems ($[{\color{green}c^-}, {\color{green}c^+}] = [0, 1]$) - Edmond's blossom algorithm 🌸 --- ### Min-Cost Flow Problem (MCFP) 💰 - Problem Formulation: $$\begin{array}{ll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x} \\ \text{s. t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue} A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - Algorithm idea: descent method: given a feasible ${\color{green}x_0}$, find a better solution ${\color{green}x_1} = {\color{green}x_0} + \alpha \cdot {\color{green}p}$, where $\alpha$ is positive. --- ### General Descent Method - **Input**: $f(x)$, initial $x$ - **Output**: optimal opt $x^*$ - **while** not converged, 1. Choose descent direction $p$; 2. Choose the step size $\alpha$; 3. $x := x + \alpha \cdot p$; --- ### Some Common Descent Directions - Gradient descent: $p = -\nabla f(x)^\mathsf{T}$ - Steepest descent: - $\triangle x_\text{nsd}$ = argmin$\{\nabla f(x)^\mathsf{T} v \mid \|v\|=1 \}$ - $\triangle x_\text{sd} = \|\nabla f(x)\| \triangle x_\text{nsd}$ (un-normalized) - Newton's method: $p = -\nabla^2 f(x)^{-1} \nabla f(x)$ - For convex problems, must satisfy $\nabla f(x)^\mathsf{T} p < 0$. **Note:** Here, there is a natural way to choose $p$! --- ### Min-Cost Flow Problem (II) 💰 - Let ${\color{green}x_1} = {\color{green}x_0} + \alpha \cdot {\color{green}p}$, then we have: $$\begin{array}{lll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x_0} + \alpha {\color{blue}d}^\mathsf{T} {\color{green}p} & \Rightarrow {\color{blue}d}^\mathsf{T} {\color{green}p} < 0 \\ \text{s. t.} & -{\color{green}x_0} \leq \alpha \cdot {\color{green}p} \leq {\color{green}c} - {\color{green}x_0} & \Rightarrow \text{residual graph} \\ & {\color{blue} A^\mathsf{T} } {\color{green}p} = 0 & \Rightarrow {\color{green}p} \text{ is a cycle!} \end{array}$$ - In other words, choose ${\color{green}p}$ to be a negative cycle! ➖ - Simple negative cycle, or - Minimum mean cycle --- ### Primal Method for MCFP 💧 - **Input**: $G({\color{salmon}V},{\color{lime}E}), [{\color{green}c^-}, {\color{green}c^+}], {\color{blue}d}$ - **Output**: optimal opt ${\color{green}x^*}$ - Initialize a feasible ${\color{green}x}$ and certain data structure - **while** a negative cycle ${\color{green}p}$ found in $G({\color{green}x})$, 1. Choose a step size $\alpha$; 2. **If** $\alpha$ is unbounded, **return** UNBOUNDED; 3. **If** $\alpha = 0$, **break**; 4. ${\color{green}x} := {\color{green}x} + \alpha \cdot {\color{green}p}$; 5. Update corresponding data structures - **return** OPTIMAL --- ### Remarks (VI) - In Step 4, negative cycle can be found using Bellman-Ford algorithm. ⏱️ - In the cycle cancelling algorithm, ${\color{green}p}$ is: - a simple negative cycle, or - a minimum mean cycle - A heap or other data structures are used for finding negative cycles efficiently. 🌳 - Usually $\alpha$ is chosen such that one constraint is tight. --- ### Min-Cost Potential Problem (MCPP) ⚡ - Problem formulation: $$\begin{array}{ll} \text{min} & {\color{green}c}^\mathsf{T} {\color{blue}y} \\ \text{s. t.} & {\color{blue}y} \leq {\color{blue}d}, \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y} \end{array}$$ where $c$ is assumed to be non-negative. - Algorithm: given an initial feasible ${\color{firebrick}u_0}$, find a better sol'n ${\color{firebrick}u_1} = {\color{firebrick}u_0} + \beta \cdot {\color{firebrick}q}$, where $\beta$ is positive: $$\begin{array}{lll} \text{min} & {\color{green}c}^\mathsf{T} {\color{blue}y_0} + {\color{green}c}^\mathsf{T} {\color{blue}y} & \Rightarrow {\color{green}c}^\mathsf{T} {\color{blue}y} < 0 \\ \text{s. t.} & {\color{blue}y} \leq {\color{blue}d} - {\color{green}A} {\color{firebrick}u_0} & \Rightarrow \text{residual graph} \\ & \beta {\color{green}A} {\color{firebrick}q} = {\color{blue}y} & \Rightarrow {\color{firebrick}q} \; \text{is a ``cut''!} \end{array}$$ --- ### Method for MCPP ⚡ - **Input**: $G({\color{salmon}V},{\color{lime}E}), {\color{green}c}, {\color{blue}d}$ - **Output**: optimal opt ${\color{firebrick}u^*}$ - Initialize a feasible ${\color{firebrick}u}$ and certain data structure - **while** a negative cut ${\color{firebrick}q}$ found in $G({\color{firebrick}u})$, 1. Choose a step size $\beta$; 2. **If** $\beta$ is unbounded, **return** UNBOUNDED; 3. **If** $\beta = 0$, **break**; 4. ${\color{firebrick}u} := {\color{firebrick}u} + \beta \cdot {\color{firebrick}q}$; 5. Update corresponding data structures - **return** OPTIMAL --- ### Remarks (VII) 📝 - Usually $\beta$ is chosen such that one constraint is tight. - The min-cost potential problem is the dual of the min-cost flow problem, so algorithms can solve both problems. - In the network simplex method, ${\color{firebrick}q}$ is chosen from a spanning tree data structure (for linear problems only) --- count: false class: nord-dark, middle, center ## Q&A 🎤