論文の概要: Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow

• arxiv url: http://arxiv.org/abs/2609.09295v1
• Date: Tue, 08 Sep 2026 18:00:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.770284
• Title: Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow
• Title（参考訳）: 繰り返し重み付き最小方形による固定帯ネットワーク流の探索支援
• Abstract要約: 固定電荷ネットワークフロー問題(FCNFP)は、離散アークアクティベーション決定と連続的なフロー割り当てを結合する。 本稿では,反復的に再重み付けされた最小二乗フレームワークに基づく拡張性のある連続最適化FCNFPを提案する。
• 参考スコア（独自算出の注目度）: 8.021197489470756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: 固定電荷ネットワークフロー問題(FCNFP)は、離散アーク活性化決定と連続フローアロケーションを結合し、様々なネットワーク設計や資源アロケーション問題に対して、標準的ではあるが計算的に挑戦的なモデルとなる。 特別な混合整数線形プログラミングの定式化は固定電荷構造を忠実にとらえるが、大規模ネットワークでは解決が困難になることが多い。 大規模単一商品FCNFPのための拡張性のある連続最適化アルゴリズムを,反復再重み付き最小二乗(IRLS)フレームワークに基づいて提案する。 この方法は不連続な固定電荷と線形アークコストの目標を滑らかな非凸Lasry-Lionsサロゲートに置き換え、重み付き二次流サブプロブレムの列を解く。 各サブプロブレムは、ニュートン系が重み付きグラフ-ラプラシアン構造を持ち、現代のラプラシアン解法の使用を可能にする、暖かく開始された双対半滑らかニュートン法によって解決される。 また, 目標駆動型摂動再起動と, IRLS と補完的な FCNFP ヒューリスティックスによる支援を併用したアンカー・ユニニオン制限探索を組み込んだアルゴリズム変異体を開発した。 410ベンチマーク, 合成, 大規模インスタンスの計算実験により, 評価されたスケーラブルなFCNFPアルゴリズムの中で, 平均誤差が1.316 %, 勝利率が90.0 %であることがわかった。 その結果,スムーズな連続最適化とサポートレベル探索を組み合わせることは,大規模FCNFPの高品質な実現可能なソリューションを作成する上で有効な戦略であることが示唆された。

関連論文リスト

• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。 既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。 提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
  論文  参考訳（メタデータ） (2025-10-15T16:13:44Z)
• Learning based convex approximation for constrained parametric optimization [11.379408842026981]
  本稿では、制約付き最適化問題を解決するために、入力ニューラルネットワーク(ICNN)に基づく自己教師付き学習フレームワークを提案する。 厳密な収束解析を行い、このフレームワークが元の問題のKKT近似点に収束することを示す。 提案手法は精度,実現可能性,計算効率の両立を実現している。
  論文  参考訳（メタデータ） (2025-05-07T00:33:14Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  分散サーバ(DFL)はクライアント・クライアント・アーキテクチャへの依存をなくす。 非滑らかな正規化はしばしば機械学習タスクに組み込まれる。 本稿では,これらの問題を解決する新しいDNCFLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-17T08:32:25Z)
• A Learned Proximal Alternating Minimization Algorithm and Its Induced Network for a Class of Two-block Nonconvex and Nonsmooth Optimization [4.975853671529418]
  本研究では,学習可能な2ブロック非平滑問題の解法として,一般学習型交互最小化アルゴリズムLPAMを提案する。 提案するLPAM-netはパラメータ効率が高く,いくつかの最先端手法と比較して良好な性能を示す。
  論文  参考訳（メタデータ） (2024-11-10T02:02:32Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep Unrolling(ディープ・アンローリング)は、トレーニング可能なニューラルネットワークの層に切り捨てられた反復アルゴリズムをアンロールする、新たな学習最適化手法である。 アンロールネットワークの収束保証と一般化性は、いまだにオープンな理論上の問題であることを示す。 提案した制約の下で訓練されたアンロールアーキテクチャを2つの異なるアプリケーションで数値的に評価する。
  論文  参考訳（メタデータ） (2023-12-25T18:51:23Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。 本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。 ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
  論文  参考訳（メタデータ） (2022-10-27T07:15:55Z)
• An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity [13.27709100571336]
  近年,グループ正規化期間を持つリーク型ReLUネットワークが広く利用されている。 定常点を決定論的に計算する手法が存在しないことを示す。 本稿では,新しいモデルを解くための不正確な拡張ラグランジアンアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-11T11:53:15Z)
• Resource-constrained Federated Edge Learning with Heterogeneous Data: Formulation and Analysis [8.863089484787835]
  ヘテロジニアスデータによる不均一な統計的課題を解決するために, 分散されたニュートン型ニュートン型トレーニングスキームであるFedOVAを提案する。 FedOVAはマルチクラス分類問題をより単純なバイナリ分類問題に分解し、アンサンブル学習を用いてそれぞれの出力を結合する。
  論文  参考訳（メタデータ） (2021-10-14T17:35:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。