論文の概要: Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2006.01610v1
• Date: Tue, 2 Jun 2020 13:54:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-25 23:27:29.927847
• Title: Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization
• Title（参考訳）: 組合せ最適化のための強化学習と制約プログラミングの組み合わせ
• Authors: Quentin Cappart and Thierry Moisan and Louis-Martin Rousseau and Isabeau Pr\'emont-Schwarz and Andre Cire
• Abstract要約: 目標は、有限個の可能性の集合の中で最適解を見つけることである。 深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。 制約プログラミング(CP)は最適化問題を解決する汎用ツールである。 本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
• 参考スコア（独自算出の注目度）: 5.669790037378094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization has found applications in numerous fields, from aerospace to transportation planning and economics. The goal is to find an optimal solution among a finite set of possibilities. The well-known challenge one faces with combinatorial optimization is the state-space explosion problem: the number of possibilities grows exponentially with the problem size, which makes solving intractable for large problems. In the last years, deep reinforcement learning (DRL) has shown its promise for designing good heuristics dedicated to solve NP-hard combinatorial optimization problems. However, current approaches have two shortcomings: (1) they mainly focus on the standard travelling salesman problem and they cannot be easily extended to other problems, and (2) they only provide an approximate solution with no systematic ways to improve it or to prove optimality. In another context, constraint programming (CP) is a generic tool to solve combinatorial optimization problems. Based on a complete search procedure, it will always find the optimal solution if we allow an execution time large enough. A critical design choice, that makes CP non-trivial to use in practice, is the branching decision, directing how the search space is explored. In this work, we propose a general and hybrid approach, based on DRL and CP, for solving combinatorial optimization problems. The core of our approach is based on a dynamic programming formulation, that acts as a bridge between both techniques. We experimentally show that our solver is efficient to solve two challenging problems: the traveling salesman problem with time windows, and the 4-moments portfolio optimization problem. Results obtained show that the framework introduced outperforms the stand-alone RL and CP solutions, while being competitive with industrial solvers.
• Abstract（参考訳）: 組合せ最適化は航空宇宙、交通計画、経済など様々な分野で応用されている。 目標は、有限個の可能性の中で最適な解を見つけることである。 組合せ最適化で直面するよく知られた課題は、状態空間の爆発問題である。可能性の数は問題のサイズによって指数関数的に増加するため、大きな問題では解決できない。 近年、深部強化学習(DRL)はNP-hard組合せ最適化問題を解決するための優れたヒューリスティックを設計することを約束している。 しかし, 現状のアプローチには, 1 つの欠点がある。(1) 主に旅行セールスマンの問題に焦点をあてるが, 他の問題にも容易に拡張できないこと (2) 改善や最適性を証明するための体系的な方法のない近似解のみを提供する。 別の文脈では、制約プログラミング(cp)は組合せ最適化問題を解決する汎用ツールである。 完全な検索手順に基づいて、実行時間を十分に大きなものにすれば、常に最適な解決策が見つかる。 cpを実際に使うのが簡単でない重要な設計選択は分岐決定であり、探索空間の探索の仕方を指示する。 本研究では,組合せ最適化問題を解くために,drl と cp に基づく汎用およびハイブリッド手法を提案する。 私たちのアプローチの核心は、両方のテクニック間の橋渡しとして機能する動的プログラミングの定式化に基づいています。 我々は,タイムウインドウによるトラベルセールスマン問題と4モーメントポートフォリオ最適化問題という2つの課題を解決するために,我々の解法が効率的であることを実験的に示す。 その結果,本フレームワークは工業用解法と競合しながら,スタンドアローンの RL および CP ソリューションよりも優れた性能を示した。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• A Novel Approach for Auto-Formulation of Optimization Problems [66.94228200699997]
  Natural Language for Optimization (NL4Opt) NeurIPS 2022コンペティションでは、最適化ソルバのアクセシビリティとユーザビリティの改善に重点を置いている。 本稿では,チームのソリューションについて述べる。 提案手法は,サブタスク1のF1スコアとサブタスク2の0.867の精度を達成し,それぞれ第4位,第3位を獲得した。
  論文  参考訳（メタデータ） (2023-02-09T13:57:06Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。 しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
  論文  参考訳（メタデータ） (2022-10-20T14:54:37Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。 このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
  論文  参考訳（メタデータ） (2022-03-04T17:06:00Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Learning for Robust Combinatorial Optimization: Algorithm and Application [26.990988571097827]
  最適化学習(L2O)は、ニューラルネットワークの強い予測力を活用することにより、最適化問題を解決するための有望なアプローチとして登場した。 本稿では,不確実な状況下で頑健な解を迅速に出力するLRCOという新しい学習ベース最適化を提案する。 その結果、LRCOは、非常に少ない複雑さで、最悪のケースコストとランタイムを大幅に削減できることがわかった。
  論文  参考訳（メタデータ） (2021-12-20T07:58:50Z)
• Comparing Heuristics, Constraint Optimization, and Reinforcement Learning for an Industrial 2D Packing Problem [58.720142291102135]
  カットとパッケージングの問題は、ビジネスの収益に直接影響を与えるさまざまな業界で起きている。 機械学習は、このような問題を解決するためにますます使われています。
  論文  参考訳（メタデータ） (2021-10-27T15:47:47Z)
• Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
  本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。 本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。 可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
  論文  参考訳（メタデータ） (2021-07-02T06:46:23Z)
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
  本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。 通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-27T07:15:25Z)

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

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