論文の概要: Training a Deep Q-Learning Agent Inside a Generic Constraint Programming Solver

• arxiv url: http://arxiv.org/abs/2301.01913v1
• Date: Thu, 5 Jan 2023 05:13:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-06 13:33:17.921437
• Title: Training a Deep Q-Learning Agent Inside a Generic Constraint Programming Solver
• Title（参考訳）: ジェネリック制約プログラミングソルバー内でのQ-Learningエージェントの訓練
• Authors: Tom Marty (1 and 2), Tristan Fran\c{c}ois (2), Pierre Tessier (2), Louis Gauthier (2), Quentin Cappart (1), Louis-Martin Rousseau (1) ((1) \'Ecole Polytechnique de Montr\'eal, (2) \'Ecole Polytechnique, Institut Polytechnique de Paris)
• Abstract要約: 本稿では,制約型プログラミング解法内での値選択に利用できる汎用的な学習手法を提案する。 これは、深いQ-ラーニングアルゴリズム、カスタマイズされた報酬信号、異種グラフニューラルネットワークアーキテクチャの組み合わせによって実現されている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constraint programming is known for being an efficient approach for solving combinatorial problems. Important design choices in a solver are the branching heuristics, which are designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. To the best of our knowledge, it is still an open research question. Although several generic variable-selection heuristics are available in the literature, the options for a generic value-selection heuristic are more scarce. In this paper, we propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network architecture. Experiments on graph coloring, maximum independent set, and maximum cut problems show that our framework is able to find better solutions close to optimality without requiring a large amounts of backtracks while being generic.
• Abstract（参考訳）: 制約プログラミングは組合せ問題の効率的な解法として知られている。 解法における重要な設計選択は分岐ヒューリスティックスであり、探索を最小限の時間で最良の解に導くように設計されている。 しかし、これらのヒューリスティックスの開発は、問題固有の専門知識を必要とする時間を要するプロセスである。 この観察は、専門家の介入なしに機械学習を使って効率的なヒューリスティックを自動的に学習する多くの努力を動機付けてきた。 私たちの知る限りでは、まだオープンな研究課題である。 いくつかのジェネリック変数選択ヒューリスティックは文献で利用可能であるが、ジェネリック値選択ヒューリスティックの選択肢は少ない。 本稿では,制約プログラミングソルバの内部において,価値選択ヒューリスティックを得るために使用できる汎用学習手順を導入することで,この問題に取り組むことを提案する。 これは、深いq学習アルゴリズム、カスタマイズされた報酬信号、異種グラフニューラルネットワークアーキテクチャの組み合わせによって達成されている。 グラフの彩色,最大独立集合,最大カット問題に関する実験は,汎用的ながら大量のバックトラックを必要とせずに,最適に近いより良い解を見つけることができることを示した。

関連論文リスト

• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。 重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。 フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
  論文  参考訳（メタデータ） (2024-08-16T02:07:34Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Genetic-based Constraint Programming for Resource Constrained Job Scheduling [5.068093754585243]
  資源制約されたジョブスケジューリングは、鉱業に起源を持つ計算の最適化問題である。 既成のソリューションはこの問題を合理的な時間枠で十分解決できない。 本稿では,制約プログラミングの効率的な探索手法を探索する遺伝的プログラミングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-01T09:57:38Z)
• Interpretable Decision Tree Search as a Markov Decision Process [8.530182510074983]
  教師付き学習タスクに最適な決定木を見つけることは、大規模に解決する上で難しい問題である。 近年、マルコフ決定問題 (MDP) としてこの問題の枠組みを定め、深層強化学習を用いてスケーリングに取り組むことが提案されている。 そこで我々は,全ての状態に対して生成する情報理論テスト生成関数を用いて,MDPの分解能を拡大する手法を提案する。
  論文  参考訳（メタデータ） (2023-09-22T08:18:08Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  本稿では,機械学習技術を利用して正確な最適化アルゴリズムをスケールアップするフレームワークを提案する。 我々のフレームワークは、問題インスタンスのサイズを減らすために、要素を刈り取るという比較的単純なタスクを学習します。 我々のフレームワークは入力グラフのかなりの部分を取り除き、なおも最大傾きのほとんどを検出可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-05T13:10:39Z)

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

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