論文の概要: Learning Lagrangian Multipliers for the Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2312.14836v1
• Date: Fri, 22 Dec 2023 17:09:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-25 14:17:44.381660
• Title: Learning Lagrangian Multipliers for the Travelling Salesman Problem
• Title（参考訳）: 旅行セールスマン問題に対するラグランジアン乗算器の学習
• Authors: Augustin Parjadis, Quentin Cappart, Bistra Dilkina, Aaron Ferber, Louis-Martin Rousseau
• Abstract要約: 本稿では,グラフニューラルネットワークの能力を活用して問題構造を利用する,革新的な教師なし学習手法を提案する。 この手法を、旅行セールスマン問題に対する有名なヘルド・カルプ・ラグランジアン緩和に適用する。 実現可能な解を見つけることに焦点を当てた既存の文献の多くとは対照的に、我々のアプローチは両面で動作し、学習が最適性の証明を加速できることを示す。
• 参考スコア（独自算出の注目度）: 12.968608204035611
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lagrangian relaxation is a versatile mathematical technique employed to relax constraints in an optimization problem, enabling the generation of dual bounds to prove the optimality of feasible solutions and the design of efficient propagators in constraint programming (such as the weighted circuit constraint). However, the conventional process of deriving Lagrangian multipliers (e.g., using subgradient methods) is often computationally intensive, limiting its practicality for large-scale or time-sensitive problems. To address this challenge, we propose an innovative unsupervised learning approach that harnesses the capabilities of graph neural networks to exploit the problem structure, aiming to generate accurate Lagrangian multipliers efficiently. We apply this technique to the well-known Held-Karp Lagrangian relaxation for the travelling salesman problem. The core idea is to predict accurate Lagrangian multipliers and to employ them as a warm start for generating Held-Karp relaxation bounds. These bounds are subsequently utilized to enhance the filtering process carried out by branch-and-bound algorithms. In contrast to much of the existing literature, which primarily focuses on finding feasible solutions, our approach operates on the dual side, demonstrating that learning can also accelerate the proof of optimality. We conduct experiments across various distributions of the metric travelling salesman problem, considering instances with up to 200 cities. The results illustrate that our approach can improve the filtering level of the weighted circuit global constraint, reduce the optimality gap by a factor two for unsolved instances up to a timeout, and reduce the execution time for solved instances by 10%.
• Abstract（参考訳）: ラグランジアン緩和(英: lagrangian relax)は、最適化問題における制約を緩和するために用いられる多目的数学の手法であり、双対境界の生成により、実現可能な解の最適性と、制約プログラミング(重み付き回路制約など)における効率的なプロパゲータの設計を証明できる。 しかしながら、ラグランジアン乗法(例えば劣勾配法)を導出する従来の過程はしばしば計算集約的であり、大規模あるいは時間に敏感な問題に対する実用性を制限している。 そこで本研究では,グラフニューラルネットワークの能力を活用して問題構造を活用し,精度の高いラグランジアン乗算器を効率的に生成することを目的とした,教師なし学習手法を提案する。 この手法を、旅行セールスマン問題に対する有名なヘルド・カルプ・ラグランジアン緩和に適用する。 中心となる考え方は、正確なラグランジアン乗算を予測し、ヘルド=カルプ緩和境界を生成するための暖かい出発点としてそれらを用いることである。 これらの境界は、分岐とバウンドのアルゴリズムによって実行されるフィルタリングプロセスを強化するために使われる。 実現可能な解を見つけることに焦点を当てた既存の文献の多くとは対照的に、我々のアプローチは両面で動作し、学習が最適性の証明を加速できることを示す。 我々は,200都市までの事例を考慮し,メートル法トラベルセールスマン問題の様々な分布について実験を行う。 その結果、本手法は、重み付き回路のグローバル制約のフィルタリングレベルを改善し、タイムアウトまでの未解決インスタンスに対する係数2による最適性ギャップを減らし、解決インスタンスの実行時間を10%削減できることを示した。

関連論文リスト

• Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning [2.8425837800129696]
  ラグランジアン分解(LD)は、制約付き最適化問題に対して二重境界を与える緩和法である。 この研究は、制約プログラミングにおいて有効な双対境界を学習するための最初の一般的な方法を示す。
  論文  参考訳（メタデータ） (2024-08-22T19:26:29Z)
• Near-Optimal Solutions of Constrained Learning Problems [85.48853063302764]
  機械学習システムでは、振る舞いを縮小する必要性がますます顕在化している。 これは、双対ロバスト性変数を満たすモデルの開発に向けた最近の進歩によって証明されている。 この結果から, 豊富なパラメトリゼーションは非次元的, 有限な学習問題を効果的に緩和することが示された。
  論文  参考訳（メタデータ） (2024-03-18T14:55:45Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs [2.6899003881035406]
  我々は、降下を回避し、局所的な最適化を効果的に減らし、深層学習アプローチを導入する。 提案手法は, 連続緩和とラグランジアン境界とのギャップの最大85%を解消し, 降下に基づくラグランジアン法において, 高品質なウォームスタートを提供することを示す。
  論文  参考訳（メタデータ） (2023-10-23T07:53:47Z)
• Neural Fields with Hard Constraints of Arbitrary Differential Order [61.49418682745144]
  我々は、ニューラルネットワークに厳しい制約を課すための一連のアプローチを開発する。 制約は、ニューラルネットワークとそのデリバティブに適用される線形作用素として指定することができる。 私たちのアプローチは、広範囲の現実世界のアプリケーションで実証されています。
  論文  参考訳（メタデータ） (2023-06-15T08:33:52Z)
• 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 Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  深層強化学習のための線形プログラミング(LP)の定式化について検討する。 拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。 深層パラメタライズされたラグランジアン法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T13:08:06Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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