PaperActive

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

quality89

Updated 5 h ago · first seen 11 Sept 2026

paper_01M294GM0CFZYYSYZABXZP1D97

Published: 11 Sept 2026; T1 · 5 h ago
arXiv: 2609.09295; T1 · 5 h ago
Category: math.OC; T1 · 5 h ago

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.

Authors 2

Sindura Saraswathi, Christian K\"ummerle

Specification

Official page: arxiv.org/abs/2609.09295
Source:arXiv (Atom API + RSS)T1observed 5 h agohigh
Arxiv announce type: cross
Source:arXiv (Atom API + RSS)T1observed 5 h agohigh
arXiv id: 2609.09295
Source:arXiv (Atom API + RSS)T1observed 5 h agohigh
Categories: math.OC, cs.AI, cs.LG, cs.NA, math.NA
Source:arXiv (Atom API + RSS)T1observed 5 h agohigh
PDF: arxiv.org/pdf/2609.09295
Source:arXiv (Atom API + RSS)T1observed 5 h agohigh
Primary category: math.OC
Source:arXiv (Atom API + RSS)T1observed 5 h agohigh
Published: 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 5 h agohigh

Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →

Provenance

Attributed facts

Source tiers

T19

Freshest observation

5 h ago

Conflicts

None

As of

Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.

Claim history

9 claims · 9 properties

Official pageofficial_url1

Claim history for Official page
Value	Valid from → to	Status	Source	Confidence	Extractor
https://arxiv.org/abs/2609.09295	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Abstractabstract1

Claim history for Abstract
Value	Valid from → to	Status	Source	Confidence	Extractor
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.	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Arxiv announce typearxiv_announce_type1

Claim history for Arxiv announce type
Value	Valid from → to	Status	Source	Confidence	Extractor
cross	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

arXiv idarxiv_id1

Claim history for arXiv id
Value	Valid from → to	Status	Source	Confidence	Extractor
2609.09295	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Authorsauthors1

Claim history for Authors
Value	Valid from → to	Status	Source	Confidence	Extractor
Sindura Saraswathi, Christian K\"ummerle	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Categoriescategories1

Claim history for Categories
Value	Valid from → to	Status	Source	Confidence	Extractor
math.OC, cs.AI, cs.LG, cs.NA, math.NA	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

PDFpdf_url1

Claim history for PDF
Value	Valid from → to	Status	Source	Confidence	Extractor
https://arxiv.org/pdf/2609.09295	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Primary categoryprimary_category1

Claim history for Primary category
Value	Valid from → to	Status	Source	Confidence	Extractor
math.OC	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Publishedpublished_at1

Claim history for Published
Value	Valid from → to	Status	Source	Confidence	Extractor
11 Sept 2026	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →

Source documents
Source	Document	Type	Tier	Last observed	Snapshots
arXiv (Atom API + RSS)	rss.arxiv.org/rss/cs.AI	feed	T1· Official	3 h ago	1

Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.