arXiv:2609.09295v1 math.OC

고정비용 네트워크 플로우를 위한 반복 재가중 최소제곱법 기반 서포트 탐색

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

Sindura Saraswathi, Christian Kümmerle

제출 2026-09-08

한국어 초록

고정비용 네트워크 플로우 문제(fixed-charge network flow problem, FCNFP)는 연속적인 플로우 할당과 이산적인 아크 활성화 결정을 결합한 문제로, 다양한 네트워크 설계 및 자원 할당 문제를 대표하지만 계산적으로 풀기 어려운 모델이다. 정확한 혼합 정수 선형 계획법(MILP) 정식화는 고정비용 구조를 충실하게 표현하지만, 대규모 네트워크에서는 풀기 어려워지는 경우가 많다. 본 논문에서는 반복 재가중 최소제곱(iteratively reweighted least-squares, IRLS) 프레임워크에 기반하여 대규모 단일 상품 FCNFP를 위한 확장 가능한 연속 최적화 알고리즘을 제안한다. 이 방법은 불연속적인 고정비용 및 선형 아크 비용 목적함수를 매끄러운 비볼록 Lasry--Lions 대리 함수(surrogate)로 대체하고, 일련의 가중 이차 플로우 부문제를 푼다. 각 부문제는 웜 스타트(warm-start)를 적용한 쌍대 준매끄러운(semismooth) 뉴턴 방법으로 풀며, 이때 뉴턴 시스템은 가중 그래프 라플라시안(graph-Laplacian) 구조를 가지므로 최신 라플라시안 솔버를 활용할 수 있다. 근본적으로 어려운 조합 최적화 문제에서 발견되는 아크 서포트(support)를 더욱 개선하기 위해, 목적함수 기반 섭동 재시작(objective-driven perturbation restarts)과 앵커 합집합 제한 탐색(anchor-union restricted search)을 결합한 알고리즘 변형도 개발한다. 이 변형은 IRLS가 발견한 서포트와 상호 보완적인 FCNFP 휴리스틱이 발견한 서포트를 함께 활용한다. 410개의 벤치마크, 합성, 대규모 인스턴스에 대한 계산 실험 결과, 제안 방법은 평가된 확장 가능한 FCNFP 알고리즘 중 가장 우수한 목적함수 품질을 얻었으며, 시간 제한이 있는 MILP 기준 해 대비 평균 격차는 $1.316\%$, 비(非)MILP 방법 중 승리 또는 동률 비율은 $90.0\%$였다. 이러한 결과는 매끄러운 연속 최적화와 서포트 수준 탐색을 결합하는 것이 대규모 FCNFP에 대해 고품질 실행 가능해를 만들어내는 효과적인 전략임을 보여준다.

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.09295v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.