The fixed-charge network flow problem (FCNFP) couples continuous flow allocation with discrete arc‑activation decisions, making it a canonical model for network design and resource allocation, yet it becomes computationally hard on large networks. Exact mixed‑integer linear programming (MILP) formulations capture the fixed‑charge structure faithfully but often fail to scale. This paper proposes a scalable continuous‑optimization algorithm based on an iteratively reweighted least‑squares (IRLS) framework for large‑scale single‑commodity FCNFP. The method replaces the discontinuous fixed‑charge and linear arc cost objective with a smooth non‑convex Lasry–Lions surrogate and solves a sequence of weighted quadratic flow subproblems. Each subproblem is tackled by a warm‑started dual semismooth Newton method whose Newton systems have a weighted graph‑Laplacian structure, enabling the use of modern Laplacian solvers. To further improve the discovered arc supports of the underlying combinatorial problem, we develop a variant that incorporates objective‑driven perturbation restarts and an anchor‑union restricted search, jointly leveraging supports found by IRLS and complementary FCNFP heuristics. Computational experiments on 410 benchmark, synthetic, and large‑scale instances show that our method achieves the best objective quality among 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 non‑MILP methods. These 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.
Review