AI Research Portal

This paper introduces the first minimum-cost network flow algorithm augmented with a dual prediction, building upon the classic ɛ-relaxation algorithm. The core idea is to leverage machine-learned predictions of optimal dual solutions to warm-start the ɛ-relaxation process, thereby provably and practically accelerating its performance. The method provides time complexity bounds that are consistent (improving with small prediction error) and robust (retaining classic worst-case bounds with large error). Empirically, the approach demonstrates significant speedups on two applications: traffic networks and chip escape routing.

The paper addresses several bottlenecks in solving minimum-cost network flow problems:

Time-consuming for large instances: Despite polynomial time complexity, solving large-scale minimum-cost flow instances (e.g., networks with millions of nodes and edges) is time-consuming in practice.
Pessimistic worst-case time complexity analysis: Traditional worst-case time complexity analyses are often overly pessimistic, leading to loose complexity bounds that do not reflect practical algorithm behaviors. For example, the successive shortest path algorithm may theoretically require an exponential number of iterations but often runs faster in practice.

First minimum-cost flow algorithm with dual predictions: The paper proposes the first minimum-cost flow algorithm that is augmented with a dual prediction, based on the ɛ-relaxation algorithm.
Provable time complexity improvement: It is shown that the complexity of the ɛ-relaxation algorithm for minimum-cost flow can be provably improved by a dual prediction.
Consistent and robust time complexity bounds: The proposed algorithm provides time complexity bounds in terms of the infinity norm prediction error, which are consistent (reduces running time with small error) and robust (retains worst-case complexity with completely erroneous prediction).
Sample complexity bounds for PAC-learning: The paper proves sample complexity bounds for PAC-learning the prediction from data.
Empirical validation on real-world applications: The theoretical results are empirically validated on traffic networks and chip escape routing, demonstrating significant speedups.

The proposed method enhances the ɛ-relaxation algorithm for minimum-cost network flow by incorporating a dual prediction.

Problem Formulation The linear minimum-cost network flow problem (MCF) is formulated as: min Σ Aij xij, (vi,vj) EE subj. to Σ xij - Σ xji = Si, ∀i ∈ V, (vi,vj) EE (vj,vi)∈E bij ≤ xij ≤ Cij, ∀ (vi, vj) ∈ E. The dual problem of MCF is: max Σ qij (Pi - Pj) + Σ Sipi, p (vi,vj) EE Vi EV where qij(Pi - Pj) is defined as: qij(Pi - Pj) = { (aij + Pj - Pi) bij if aij + Pj - Pi ≥ 0, (aij + Pj - Pi)Cij if aij + Pj - Pi < 0.

ɛ-relaxation Algorithm with Dual Prediction The method uses a warm-start approach for the ɛ-relaxation algorithm. Warm-start ɛ-relaxation (Algorithm 1):

Preprocessing: The predicted dual solution p is shifted to make min_i p_i = 0.
Clipping: The values of p are clipped to ensure 0 < p ≤ (n - 1)C.
Run ɛ-relaxation: The ɛ-relaxation algorithm is then run with this preprocessed and clipped p as the initial dual solution.

Cost-scaling for warm-start ɛ-relaxation (Algorithm 2): To improve scalability, the warm-start ɛ-relaxation is combined with a cost-scaling trick.

Preprocessing: Same as Algorithm 1.
Scaling Parameter: Let T be the maximal integer such that c^T < ||p - p*||∞.
Initialization: Initialize the dual p(T) ← [(n + 1)p/c^T].
Iterative Scaling: For t from T-1 down to 0:
- Let p' ← cp(t+1).
- Run ɛ-relaxation with initial dual p', scaled edge costs a(t) = [(n + 1)a/c^t], and ɛ = 1 to get dual solution p(t).
Return: The optimal flow for the dual p(0).

Learning the Dual Prediction

Fixed Prediction: For traffic networks with fixed topology and random edge costs, a fixed expected optimal dual solution can be learned from collected data by minimizing a surrogate loss: min (1/k) Σ log ||p - p(i) + ∆i||∞, p∈R^n, ∆∈R k i=1 where p(i) is the optimal dual for instance a(i), and ∆i is a shift value.
Feature-based Predictor: For escape routing, a convolutional neural network (CNN) model is used to infer the prediction from problem instance features.

Network Representation: A directed graph G = (V, E) with |V| = n nodes and |E| = m edges. Each edge (vi, vj) has a cost aij and capacity (bij, Cij) with 0 ≤ bij ≤ Cij. Each node vi has a supply si ∈ R.
Assumption: All capacities and supplies are integers, leading to an integral optimal solution. C = max(vi,vj)∈E |aij| is the maximum scale of edge costs.
Time Complexity (Algorithm 1): O (min {n³ + n²ɛ⁻¹||p – p*||∞, n³ɛ⁻¹C}). For 0/1 flow instances, this improves to O (min {mn + mɛ⁻¹||p – p*||∞, mnɛ⁻¹C}).
Time Complexity (Algorithm 2, with cost-scaling): O (min {n³ log ||p – p*||∞, n³ log(nC)}). For 0/1 flow instances, this improves to O (min {mn log ||p – p*||∞, mn log(nC)}).
Sample Complexity (Fixed Prediction): For PAC-learning a fixed prediction, the sample complexity k is Ω((n²/ɛ²) (n log(nC) + log(1/δ))).
Sample Complexity (Feature-based Predictor): For a neural network model h ∈ H, the sample complexity k is Ω((ndnn/ɛ²) (n log(nC) + log(1/δ))), where dnn is the pseudo-dimension of the neural network architecture.
Neural Network Architecture (Escape Routing):
- Input: A 3-channel (w + 1) × (h + 1) feature map. The three features are: binary value for obstacle occupation, shortest path distance to the nearest pin, and shortest path distance to the boundary.
- Normalization: Inputs and outputs are divided by max(w, h) to scale values to [0, 1].
- Model: A fully convolutional neural network with a UNet-style architecture.
- Layers: Transforms input into 16-channel features using a 3 × 3 convolution kernel. The backbone has two downsampling and two upsampling blocks, each containing two 3 × 3 convolution layers and two group normalization layers. Residual connections link downsampling and upsampling layers with the same feature size.
- Output: A (w + 1) × (h + 1) matrix representing the predicted dual, produced by a 3 × 3 convolution kernel.
- Loss: Average mean-square loss (l2 norm error).
Optimization: Not stated in the paper for neural network training.
Data Augmentation: Not stated in the paper.
Data Handling: Not stated in the paper.
Implementation Details: Not stated in the paper.

Applications:
- Traffic networks (road network instances)
- Escape routing (chip escape routing instances)
Baselines:
- ɛ-R (ɛ-relaxation without prediction)
- NS (Network Simplex)
- SSP (Successive Shortest Paths)
Metrics: Running time (sec), Speedup (x), Total Iteration Number.
Numeric Results:
- Traffic Networks:
  - Average speedup: 12.74x (ɛ-R with prediction vs. ɛ-R without prediction).
  - Average running times (sec):
    - ɛ-R (p.): 1.00
    - ɛ-R: 12.74
    - NS: 12.08
    - SSP: 38.19
  - Specific instances show speedups ranging from 6.2x to 21.4x.
- Escape Routing:
  - Average speedup: 1.64x (ɛ-R with prediction vs. ɛ-R without prediction).
  - Average running times (sec):
    - ɛ-R (p.): 1.00
    - ɛ-R: 1.64
    - NS: 11.19
    - SSP: 7.53
  - Specific instances show speedups ranging from 1.1x to 2.3x.
Runtime/Training Cost:
- For traffic networks, the algorithm achieves approximately 6.2 ~ 21.4x speedup.
- For escape routing, the algorithm achieves approximately 1.1 ~ 2.3x speedup.
- The paper notes that for 0/1 flow instances (like paths_* groups in traffic networks), ɛ-relaxation performs better, even outperforming network simplex without predictions.

Discreteness of rounding: The empirical curves for running time and total iterations are "not quite smooth due to the discreteness of rounding in Algorithm 2."
Dependency on prediction error knowledge: Algorithm 2 theoretically requires knowledge of ||p – p*||∞. While this can be eliminated by guessing T, in practice, the value of T is tuned empirically based on the learning error.

Method evidence: "In this work, we propose the first minimum-cost flow algorithm with dual predictions, based on a classic algorithm, ɛ-relaxation (Bertsekas 1986). We show that a dual prediction can provably and practically accelerate ɛ-relaxation." (section: Introduction)
Result evidence: "Experimental results illustrate 12.74x and 1.64× average speedup on two applications." (section: Abstract)
Limitation evidence: "The curves are not quite smooth due to the discreteness of rounding in Algorithm 2." (section: Synthesized predictions)

Minimum-Cost Network Flow with Dual Predictions

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures