PaperlayerView exact revision on arXiv

Source-linked AI summary

Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow

Sindura Saraswathi, Christian Kümmerle

arXiv:2609.09295v1math.OCcs.AIcs.LGmath.NA

TL;DR

FCNFP requires continuous flow allocation alongside discrete arc activation, while exact MILP methods can struggle on large networks. The paper develops an IRLS algorithm using a smoothed Lasry–Lions surrogate and support-level search. Across 410 instances, it achieves the best objective quality among evaluated scalable FCNFP methods.

  • Problem

    FCNFP combines continuous flow allocation with discrete arc-activation decisions, and exact MILP methods can become difficult to solve on large instances.

  • Method

    The method uses IRLS with a smooth Lasry–Lions surrogate, weighted continuous flow subproblems, perturbation restarts, and anchor-union restricted search.

  • Results

    Across 410 instances, the method achieves the best objective quality among evaluated scalable FCNFP heuristics, with a 1.316% mean gap to the MILP reference.

  • Takeaways & Limitations

    Combining smooth continuous optimization with structured support exploration is an effective strategy for producing high-quality feasible solutions to large-scale FCNFP.

Abstract

from arXiv · show

The fixed-charge network flow problem (FCNFP) couples continuous flow allocation with discrete arc-activation decisions, making it a canonical but computationally challenging model for a variety of network design and resource allocation problems. Exact mixed-integer linear programming formulations capture the fixed-charge structure faithfully, but often become difficult to solve on large networks. We propose a scalable continuous-optimization algorithm for large-scale single-commodity FCNFP based on an iteratively reweighted least-squares (IRLS) framework. The method replaces the discontinuous fixed-charge and linear arc cost objective with a smooth nonconvex Lasry--Lions surrogate and solves a sequence of weighted quadratic flow subproblems. Each subproblem is solved by a warm-started dual semismooth Newton method whose Newton systems have weighted graph-Laplacian structure, enabling the use of modern Laplacian solvers. To further improve the discovered arc supports of the challenging underlying combinatorial problem, we also develop an algorithmic variant that incorporates objective-driven perturbation restarts and an anchor-union restricted search that jointly leverages supports discovered by IRLS and by complementary FCNFP heuristics. Computational experiments on 410 benchmark, synthetic, and large-scale instances show that our method obtains the best objective quality among the evaluated scalable FCNFP algorithms, with a mean gap of $1.316\%$ to a time-limited MILP reference and a win-or-tie rate of $90.0\%$ among the non-MILP methods. The results indicate that combining smooth continuous optimization with support-level search is an effective strategy for producing high-quality feasible solutions to large-scale FCNFP.

I. INTRODUCTION

FCNFP combines continuous flow allocation with discrete arc activation, making large instances difficult for exact methods. The paper proposes IRLS with support-improvement search to produce high-quality feasible solutions without binary optimization.

  • FCNFP routes flow under balance and capacity constraints while minimizing proportional costs and fixed charges on activated arcs.
  • Exact MILP formulations capture fixed-charge structure but become expensive at scale, failing to prove optimality on all 1000-node, 20,000-arc instances in the experiments.
  • IRLS replaces the discontinuous fixed-plus-linear objective with a Lasry–Lions-smoothed nonconvex surrogate and iteratively penalizes small-flow arcs.
  • Support improvement uses objective-driven perturbation restarts and anchor-union restricted searches that combine IRLS and external heuristic supports.
  • 410 instances yield a 1.316% mean gap to the MILP reference and a 90.0% win-or-tie rate among non-MILP methods.

II. RELATED WORK

FCNFP is computationally difficult because exact methods scale poorly with binary arc-activation decisions. Prior approximation methods exploit network-flow structure, while this work uses iteratively smoothed quadratic surrogates instead of linear or bilinear alternatives.

  • Existing FCNFP Solvers: FCNFP is NP-hard, and exact MILP or branch-and-cut methods have limited scalability because of binary arc-activation variables.
  • Existing FCNFP Solvers: DSSP replaces fixed charges with flow-dependent per-unit slopes and solves a sequence of linear min-cost-flow subproblems.
  • Proposed Method: The proposed method avoids full mixed-integer search by solving continuous network-flow subproblems based on Lasry–Lions-smoothed surrogate objectives.
  • Proposed Method: Unlike slope scaling and bilinear reformulations, the method uses quadratic subproblems whose surrogate family converges to the original FCNFP objective as smoothing vanishes.
  • Smoothing Strategies and IRLS Framework: Smoothing can regularize nonconvex landscapes by exposing descent directions and delaying premature commitment to poor local supports.
  • Efficient Laplacian Solvers: Modern graph-Laplacian solvers provide nearly-linear-time tools relevant to the scalable solution of the method’s network systems.

III. PROBLEM FORMULATION

The fixed-charge network flow problem assigns flows on a directed capacitated network while satisfying node demands. Its central difficulty is the discontinuous fixed charge activated whenever an edge carries nonzero flow.

  • Network Definition: The network has n nodes and m edges, with each edge characterized by flow, capacity, proportional cost, and fixed cost.
  • Network Definition: The incidence matrix and demand vector impose flow conservation, with positive sink demand, negative source demand, and zero transshipment demand.
  • Feasible Set: Feasible flows satisfy Cf = d and 0 ≤ f_e ≤ c_e for every edge.
  • Fixed-Charge Structure: An edge’s fixed charge is activated exactly when its flow is nonzero, corresponding to opening that edge for flow.
  • Feasible Set: The feasible-flow set is F = {f ∈ R^m : Cf = d, 0 ≤ f ≤ c}.

A. Lasry–Lions Double Envelope Combined Surrogate

The method replaces the discontinuous fixed-plus-linear edge cost with a smooth, nonconvex Lasry–Lions surrogate that preserves support promotion. Two smoothing parameters control its three regimes, and decreasing the smoothing contracts the surrogate toward the original objective.

  • Surrogate Motivation: The Lasry–Lions surrogate removes the fixed-charge discontinuity while preserving the support-promoting structure of the original edge cost.
  • Surrogate Structure: The surrogate has quadratic, transition, and active-flow regimes controlled by shared parameters λ > µ > 0.
  • Surrogate Structure: Near zero, the surrogate is quadratic, keeping IRLS weights finite and the quadratic flow subproblem well defined.
  • Transition Points: The transition points are defined by x1,e = T_e(λ − µ)/λ and an edge-dependent x2,e expression, with µ capped to keep them real and ordered.
  • Smoothness: The transition-point construction makes the surrogate continuous and continuously differentiable across its three regimes.
  • Smoothing Schedule: As λ decreases, the quadratic and transition regions contract toward zero, so the surrogate more closely tracks the fixed-plus-linear objective.

B. Iteratively Reweighted Least Squares

IRLS replaces the smoothed nonconvex FCNFP objective with successive convex weighted quadratic flow models. The weights reflect local surrogate curvature, penalizing negligible-flow arcs and concentrating flow on sparse supports.

  • IRLS replaces the nonconvex surrogate at each iteration with a convex weighted quadratic model whose weights depend on the current flow.
  • The weights are derived from the local curvature of the Lasry–Lions surrogate and couple each quadratic subproblem to its local geometry.
  • Small flows receive larger weights, making negligible-flow arcs increasingly expensive, while larger active flows receive smaller weights.
  • The proportional cost term handles active flow, while the αb_e/|f_e|^2 term acts as an ℓ0-like fixed-charge penalty.
  • Under capped parameters, exact weights and updates form a majorization–minimization scheme for the fixed-parameter surrogate.

C. Weighted Quadratic Program Solver

Each weighted quadratic flow subproblem is solved through a warm-started dual semismooth Newton method. Its Newton systems reduce to weighted graph Laplacians on free arcs, supporting scalable solves.

  • The dual semismooth Newton method solves each weighted quadratic subproblem by finding a root of the dual residual.
  • Only free arcs contribute to the Newton system, which is a weighted graph Laplacian on the currently free subgraph.
  • The solver removes constant-potential gauge freedom by mean-centering and uses predictor-based regularized line-search corrections instead of a degenerate zero initialization.
  • Each Newton system costs eO(m log(1/ϵ)), giving eO(K s̄ m log(1/ϵ)) work over K outer iterations with s̄ average Newton steps.In experiments, s̄ stayed below 4 across a 200-fold range in m.
  • Weights are clipped to [10^-12, 10^12], and failed SSN solves fall back to a primal-dual interior-point method using the same Laplacian structure.

IV. ALGORITHM

The algorithm alternates weighted-flow solves, acceptance checks, flow-gap detection, continuation, and support refitting. It retains the best feasible candidate under the true objective while refining sparse support estimates.

  • Algorithm 1 computes IRLS weights, solves a weighted quadratic subproblem, accepts a non-increasing trial iterate, and updates flow-gap statistics.
  • The reported solution is the best feasible candidate encountered, scored under J_true, with rejected steps handled by backtracking or retaining the current flow.
  • Stages advance when relative flow change falls below 10^-3, line search rejects a step, or six weighted-QP solves occur, prompting more aggressive λ reduction.
  • The widest ratio gap in sorted flow magnitudes defines K_gap and ρ_gap, which guide λ updates and support refitting.
  • When ρ_gap ≥ 10 and the inferred support is bounded, the method refits a linear min-cost flow on the estimated support to obtain feasible candidates.

V. SMOOTHING CONTINUATION SCHEME

The continuation scheme progressively sharpens the smoothed surrogate toward the fixed-charge objective while using flow-gap information to update λ. Fixed-parameter descent provides stability, whereas continuation changes the surrogate across stages.

  • The smoothed objective converges pointwise to the true objective as λ decreases along an admissible path, motivating progressive sharpening.
  • The algorithm decreases λ stage-wise and sets µ = min{λ/2, min_e µ_max,e(λ)} at each parameter update.
  • Initial λ scales differ by initialization: sparse starts use λ_0 = 10^-2 max{f_med^2/(2b_med), 1}, whereas dense starts use λ_0 = 10^2 max{max_e |f_e^(0)|, 1}.
  • The gap-based update uses λ_gap = f_down^2/(2b_rep), with slower within-stage reduction and accelerated reduction across stage boundaries.
  • Fixed-pair acceptance enforces numerical nonincrease, while continuation supplies sharpening; the best feasible incumbent remains nonincreasing under J_true.

VI. ALGORITHMIC LAYERS

The algorithm uses layered IRLS initialization, perturbation, and anchor-union restricted search to improve feasible supports without binary activation variables. Each layer expands exploration while retaining candidates scored by the true fixed-charge objective.

  • Design rationale: The layered design addresses nonconvex start dependence by combining continuous reweighting with structured support exploration.Each layer maintains the best feasible solution under the true fixed-charge objective Jtrue.
  • Layer 1: Multi-start IRLS: Layer 1 runs IRLS from five complementary feasible initializations to access multiple plausible support regions without binary activation variables.Duplicate supports are removed before separate IRLS runs.
  • Layer 2: Objective-driven perturbation restarts: Layer 2 perturbs Layer 1 supports by suppressing expensive active arcs and opening promising inactive arcs, then projects candidates back onto the feasible flow polytope.Surviving projections become new IRLS starts after ranking by objective values, support changes, and active-arc counts.
  • Layer 3: Anchor-union restricted IRLS: Layer 3 forms union supports from IRLS candidates and ADSSP anchor supports, then reruns IRLS on restricted subgraphs.Duplicate, empty, and infeasible supports are discarded before restricted refits and refinements.
  • Layer 3: Anchor-union restricted IRLS: Restricted candidates are refitted, reoptimized with IRLS, and locally refined by deleting expensive active arcs or reintroducing promising inactive arcs.The search keeps only feasible improvements under the original fixed-charge objective.

VII. EXPERIMENTS

The experiments evaluate the layered method against heuristic baselines and a time-limited MILP reference on 410 instances. L3 provides the strongest heuristic objective quality, while additional layers improve gaps but increase runtime relative to faster methods.

  • Evaluation setup: 410 instances from benchmark, synthetic, and large-scale families are evaluated against MCF, DSSP, ADSSP, and a MILP reference.The MILP reference is either a certified optimum or a time-limited feasible incumbent.
  • Aggregate results: L3 achieves the best heuristic objective quality, with a 1.316% mean gap and 0.131% median gap to the MILP objective.MILP proves optimality on 235 of 410 instances.
  • Layer ablation: L3 without anchors still outperforms ADSSP, indicating that its gains do not depend on anchor supports alone.The variant is denoted L3−.
  • Layer ablation: L3 reduces the mean gap to the best displayed heuristic from 2.163% for IRLS to 1.106% with L2 and 0.140% with L3.The comparison isolates the contributions of the heuristic layers without relying on a MILP reference.
  • Aggregate results: L3 is best or tied-best on 90.0% of instances, and its advantage persists across instance scales and MILP certification status.The latter breakdown is reported in the supplementary material.
  • Runtime tradeoff: Runtime results show a quality–time tradeoff: MCF and ADSSP are attractive immediately, whereas L3 is more expensive but remains cheaper than MILP on average.L3 performs multiple IRLS solves, restricted refits, and support refinements.

VIII. CONCLUSION

The paper presents IRLS with smoothing and structured support exploration as a scalable approach to fixed-charge network flow. Across 410 instances, the method achieves the best objective quality among evaluated FCNFP baselines, including large instances where MILP cannot certify optimality.

  • Method: The method replaces discontinuous fixed-plus-linear costs with a smooth Lasry–Lions surrogate and solves weighted quadratic flow subproblems using Laplacian-structured linear algebra.Perturbation restarts and anchor-union restricted search augment the continuous reweighting process.
  • Conclusion: Across 410 instances, the method achieves the best objective quality among evaluated FCNFP baselines, including large-scale instances where MILP cannot certify optimality.The results support combining smooth continuous optimization with structured support exploration.

A. Derivation of the Lasry–Lions Surrogate

The paper derives a smooth, continuously differentiable Lasry–Lions surrogate for the discontinuous fixed-charge arc objective. A logarithmic active-flow tail preserves fixed-charge information for IRLS while the surrogate converges to the original objective as smoothing vanishes.

  • The per-edge fixed-charge objective is J(f) = r|f| + b 1{|f| > 0}, with nonnegative proportional and fixed costs.
  • The exact Lasry–Lions construction uses two parameters, 0 < µ < λ, and combines quadratic, transition, and linear-tail regimes.The derivation characterizes the Moreau envelope, double envelope, branch maximizers, and transition points.
  • Because the exact linear tail would remove the fixed charge from IRLS weights, the implemented surrogate replaces it with a logarithmic continuation.The logarithmic tail retains fixed-charge information while preserving the two Lasry–Lions parabolic regimes near the origin.
  • The tail transition is selected through a matching condition whose larger root preserves the exact-envelope transition point as the logarithmic coefficient vanishes.The smaller root instead converges to zero.
  • As λ decreases along an admissible path, the surrogate converges pointwise to J(x), while implementation caps µ to maintain the admissible domain across edges.The convergence proof covers both positive fixed-cost and zero fixed-cost cases.
  • The resulting surrogate is continuously differentiable at the origin and both transition points, with matching values and derivatives across branches.The proof checks the joins at x1 and x2 directly and uses evenness for negative flow values.

H. Additional Experimental Results

Across dataset families and MILP termination statuses, L3 consistently delivers the strongest heuristic objective quality. Ablations indicate that its advantage comes from complementary support-search mechanisms rather than either anchor supports or IRLS-based union search alone.

  • L3 attains the best heuristic objective quality consistently across dataset families, including larger-scale instances where MILP often fails to prove optimality.
  • On 235 instances with certified MILP optima, L3 records mean and median gaps of 1.48% and 0.014%, respectively.
  • On 175 instances with time-limited MILP incumbents, L3 records mean and median gaps of 1.10% and 0.329%, respectively.
  • L3’s 87.6% win/tie rate in the ablation table is not directly comparable to the main paper’s 90.0% because the method pools differ.
  • Removing ADSSP anchors degrades L3 by 0.757 percentage points, while the anchor-free variant still wins or ties against ADSSP on 280/410 instances.
  • The ablations show that ADSSP anchors and IRLS-based union search are complementary contributors to L3’s performance.
Loading 2609.09295v1…