Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow
Abstract
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.
Related
- Distributed Algorithm for Linear Least Squares Problems via Iteratively Preconditioning by Successive Over-Relaxation
- Cross-validated feature selection using least-squares support vector machines for binary classification
- FOSLS-deRhaNN: native de Rham neural classes for H(div) and H(curl) with applications to first-order system least-squares neural network methods for partial differential equations
- A Bregman inertial iteratively regularized extragradient method for bilevel variational inequality problems
- Can the All of Us sample be reweighted to mirror a nationally representative sample? A comparison of mortality predictors
BibTeX
@misc{saraswathi2026support,
title = {{Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow}},
author = {Sindura Saraswathi and Christian Kümmerle},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09295},
eprint = {2609.09295},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09295},
}
RIS
TY - UNPB
TI - Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow
AU - Sindura Saraswathi
AU - Christian Kümmerle
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09295
UR - https://arxiv.org/abs/2609.09295
AB - 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.
ER -