論文の概要: Learning to Sparsify Travelling Salesman Problem Instances

• arxiv url: http://arxiv.org/abs/2104.09345v1
• Date: Mon, 19 Apr 2021 14:35:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-20 20:04:08.988694
• Title: Learning to Sparsify Travelling Salesman Problem Instances
• Title（参考訳）: トラベリングセールスマン問題事例をスパシフィケートする学習
• Authors: James Fitzpatrick, Deepak Ajwani and Paula Carroll
• Abstract要約: プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
• 参考スコア（独自算出の注目度）: 0.5985204759362747
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In order to deal with the high development time of exact and approximation algorithms for NP-hard combinatorial optimisation problems and the high running time of exact solvers, deep learning techniques have been used in recent years as an end-to-end approach to find solutions. However, there are issues of representation, generalisation, complex architectures, interpretability of models for mathematical analysis etc. using deep learning techniques. As a compromise, machine learning can be used to improve the run time performance of exact algorithms in a matheuristics framework. In this paper, we use a pruning heuristic leveraging machine learning as a pre-processing step followed by an exact Integer Programming approach. We apply this approach to sparsify instances of the classical travelling salesman problem. Our approach learns which edges in the underlying graph are unlikely to belong to an optimal solution and removes them, thus sparsifying the graph and significantly reducing the number of decision variables. We use carefully selected features derived from linear programming relaxation, cutting planes exploration, minimum-weight spanning tree heuristics and various other local and statistical analysis of the graph. Our learning approach requires very little training data and is amenable to mathematical analysis. We demonstrate that our approach can reliably prune a large fraction of the variables in TSP instances from TSPLIB/MATILDA (>85%$) while preserving most of the optimal tour edges. Our approach can successfully prune problem instances even if they lie outside the training distribution, resulting in small optimality gaps between the pruned and original problems in most cases. Using our learning technique, we discover novel heuristics for sparsifying TSP instances, that may be of independent interest for variants of the vehicle routing problem.
• Abstract（参考訳）: NPハード組合せ最適化問題に対する高精度・近似アルゴリズムの開発時間と高精度解法の実行時間に対処するため,近年,解を見つけるためのエンドツーエンドアプローチとしてディープラーニング技術が用いられている。 しかし、表現、一般化、複雑なアーキテクチャ、数学的解析のためのモデルの解釈可能性などの問題もある。 深層学習技術を使っています 妥協として、機械学習は、数学的フレームワークにおける正確なアルゴリズムの実行時間パフォーマンスを改善するために使用できる。 本稿では,機械学習を前処理ステップとして活用し,厳密な整数型プログラミング手法を提案する。 このアプローチを,古典的なトラベルセールスマン問題のインスタンス化に応用する。 提案手法では,グラフのどの辺が最適解に属さないかを学習し,それらを除去し,グラフを分散させ,決定変数の数を著しく減少させる。 線形計画緩和,切断面探索,最小重み付きスパンディングツリーヒューリスティックス,その他の局所的および統計的なグラフ解析から得られた注意深く選択された特徴を用いる。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適しています。 本稿では,TSPLIB/MATILDA (>85%) からTSPインスタンスの変数の大部分を確実に抽出し,最適なツアーエッジの大部分を保存できることを実証する。 提案手法は,たとえトレーニング分布外にあるとしても問題インスタンスのプルーフ化に成功し,ほとんどの場合,プルーニングされた問題と元の問題との最適性ギャップを小さくする。 学習手法を用いて、車両ルーティング問題の変種に対して独立した関心を持つTSPインスタンスをスパース化するための新しいヒューリスティックスを発見する。

関連論文リスト

• Training Artificial Neural Networks by Coordinate Search Algorithm [0.20971479389679332]
  本稿では、ニューラルネットワークのトレーニングのための勾配自由座標探索(CS)アルゴリズムの効率的なバージョンを提案する。 提案アルゴリズムは、微分不可能なアクティベーション関数で使用することができ、多目的/マルチロス問題に適合する。 ANNの重みに対する最適値を求めることは、大規模な最適化問題である。
  論文  参考訳（メタデータ） (2024-02-20T01:47:25Z)
• 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)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A* [12.117737635879037]
  データ駆動計画に関する最近の研究は、コスト関数またはプランナ関数を学習することを目的としているが、両方ではない。 グラフコストやプランナーとして、平面マップの表現を改善することができる差別化可能ないつでもプランナであるNeural Weighted A*を提案します。 我々は,複数のベースラインに対して神経重み付きa*をテストし,新たなタイルベースのナビゲーションデータセットを導入することで,クレームの妥当性を実験的に示す。
  論文  参考訳（メタデータ） (2021-05-04T13:17:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。 提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。 本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
  論文  参考訳（メタデータ） (2020-02-20T11:11:32Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  本稿では,機械学習技術を利用して正確な最適化アルゴリズムをスケールアップするフレームワークを提案する。 我々のフレームワークは、問題インスタンスのサイズを減らすために、要素を刈り取るという比較的単純なタスクを学習します。 我々のフレームワークは入力グラフのかなりの部分を取り除き、なおも最大傾きのほとんどを検出可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-05T13:10:39Z)

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

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