論文の概要: LMask: Learn to Solve Constrained Routing Problems with Lazy Masking

• arxiv url: http://arxiv.org/abs/2505.17938v1
• Date: Fri, 23 May 2025 14:15:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:34.142574
• Title: LMask: Learn to Solve Constrained Routing Problems with Lazy Masking
• Title（参考訳）: LMask:遅延マスキングによる制約付きルーティング問題の解決を学ぶ
• Authors: Tianyou Li, Haijun Zou, Jiayuan Wu, Zaiwen Wen,
• Abstract要約: 動的マスキングを利用して制約付きルーティング問題に対する高品質な実現可能なソリューションを生成する新しい学習フレームワークであるLMaskを提案する。 LMaskは最先端の実現率とソリューションの品質を達成し、既存のニューラルメソッドを上回っている。
• 参考スコア（独自算出の注目度）: 4.693576188349811
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Routing problems are canonical combinatorial optimization tasks with wide-ranging applications in logistics, transportation, and supply chain management. However, solving these problems becomes significantly more challenging when complex constraints are involved. In this paper, we propose LMask, a novel learning framework that utilizes dynamic masking to generate high-quality feasible solutions for constrained routing problems. LMask introduces the LazyMask decoding method, which lazily refines feasibility masks with the backtracking mechanism. In addition, it employs the refinement intensity embedding to encode the search trace into the model, mitigating representation ambiguities induced by backtracking. To further reduce sampling cost, LMask sets a backtracking budget during decoding, while constraint violations are penalized in the loss function during training to counteract infeasibility caused by this budget. We provide theoretical guarantees for the validity and probabilistic optimality of our approach. Extensive experiments on the traveling salesman problem with time windows (TSPTW) and TSP with draft limits (TSPDL) demonstrate that LMask achieves state-of-the-art feasibility rates and solution quality, outperforming existing neural methods.
• Abstract（参考訳）: ルーティング問題は、ロジスティクス、輸送、サプライチェーン管理における幅広い応用を伴う標準的な組合せ最適化タスクである。 しかし、複雑な制約が伴うと、これらの問題の解決が著しく困難になる。 本稿では,動的マスキングを利用して制約付きルーティング問題に対する高品質な実現可能なソリューションを生成する新しい学習フレームワークであるLMaskを提案する。 LMaskはLazyMaskデコード方式を導入し、バックトラッキング機構によって実現性マスクを遅延的に洗練する。 さらに、探索トレースをモデルにエンコードするために洗練された強度埋め込みを採用し、バックトラックによって引き起こされる表現の曖昧さを緩和する。 サンプリングコストをさらに削減するため、LMaskは復号中にバックトラック予算を設定し、トレーニング中に損失関数に制約違反をペナルティ化し、この予算による不確実性に対処する。 提案手法の妥当性と確率論的最適性に関する理論的保証を提供する。 タイムウインドウ(TSPTW)とドラフトリミット(TSPDL)による旅行セールスマン問題に対する広範な実験は、LMaskが最先端の実現可能性率とソリューション品質を達成し、既存のニューラルメソッドより優れていることを示した。

関連論文リスト

• Learning for Cross-Layer Resource Allocation in MEC-Aided Cell-Free Networks [71.30914500714262]
  移動エッジコンピューティング(MEC)を援用したセルフリーネットワーク上でのクロスレイヤリソース割り当ては、データレートを促進するために、送信およびコンピューティングリソースを十分に活用することができる。 深層学習の観点からMEC支援セルフリーネットワークのサブキャリア配置とビームフォーミング最適化について検討した。
  論文  参考訳（メタデータ） (2024-12-21T10:18:55Z)
• Learning to Handle Complex Constraints for Vehicle Routing Problems [26.354311541533754]
  車両ルーティング問題(VRP)は多くの現実のシナリオをモデル化することができ、しばしば複雑な制約を伴います。 最近のニューラルメソッドは、実現可能性マスキングに基づくソリューションの構築において優れているが、複雑な制約を扱うのに苦労している。 本稿では,より複雑なVRPに向けたニューラルメソッドの能力を向上するための,新しい能動的機能改善フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-28T14:26:54Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep Unrolling(ディープ・アンローリング)は、トレーニング可能なニューラルネットワークの層に切り捨てられた反復アルゴリズムをアンロールする、新たな学習最適化手法である。 アンロールネットワークの収束保証と一般化性は、いまだにオープンな理論上の問題であることを示す。 提案した制約の下で訓練されたアンロールアーキテクチャを2つの異なるアプリケーションで数値的に評価する。
  論文  参考訳（メタデータ） (2023-12-25T18:51:23Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  3つの代表的構成課題にまたがる変圧器大言語モデルの限界について検討する。 これらのタスクは、問題をサブステップに分割し、これらのステップを正確な答えに合成する必要があります。 実験結果から,多段階合成推論を線形化部分グラフマッチングに還元することにより,トランスフォーマーLLMが構成課題を解くことが示唆された。
  論文  参考訳（メタデータ） (2023-05-29T23:24:14Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation [0.4014524824655105]
  現実世界のアプリケーションにおける車両ルーティング問題(VRP)には、様々な制約が伴うことが多い。 ソフト制約付きVRPを解くために,強化学習に基づく手法を提案する。 本稿では,3種類のVRP,TSPTW(Travelling Salesman Problem with Time Windows),CVRP(Capacitated VRP),CVRPTW(Capacitated VRP with Time Windows)に適用する。
  論文  参考訳（メタデータ） (2022-07-20T12:51:06Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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