論文の概要: Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming

• arxiv url: http://arxiv.org/abs/2102.09663v1
• Date: Thu, 18 Feb 2021 23:18:17 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-22 13:25:26.536894
• Title: Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
• Title（参考訳）: Smart Feasibility Pump:(混合)整数プログラミングのための強化学習
• Authors: Meng Qi, Mengxin Wang, Zuo-Jun Shen
• Abstract要約: 本稿では,(混合)整数プログラミング(MIP)問題に対する実現可能な解を見つけるための深層強化学習(DRL)モデルを提案する。 多くの成功者は既知の初期の実現可能なソリューションに依存しているため、MIP問題に対する実現可能なソリューションを見つけることは重要です。 マルチレイヤ認識(MLP)に加えて,制約行列の隠れ情報を取得するために,ポリシーネットワークのための新しい畳み込みネットワーク(CNN)構造を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we propose a deep reinforcement learning (DRL) model for finding a feasible solution for (mixed) integer programming (MIP) problems. Finding a feasible solution for MIP problems is critical because many successful heuristics rely on a known initial feasible solution. However, it is in general NP-hard. Inspired by the feasibility pump (FP), a well-known heuristic for searching feasible MIP solutions, we develop a smart feasibility pump (SFP) method using DRL. In addition to multi-layer perception (MLP), we propose a novel convolution neural network (CNN) structure for the policy network to capture the hidden information of the constraint matrix of the MIP problem. Numerical experiments on various problem instances show that SFP significantly outperforms the classic FP in terms of the number of steps required to reach the first feasible solution. Moreover, the CNN structure works without the projection of the current solution as the input, which saves the computational effort at each step of the FP algorithms to find projections. This highlights the representational power of the CNN structure.
• Abstract（参考訳）: 本研究では,(混合)整数プログラミング(MIP)問題に対する実現可能な解を求めるための深層強化学習(DRL)モデルを提案する。 多くの成功したヒューリスティックが既知の初期の実現可能なソリューションに依存しているため、MIP問題に対する実現可能なソリューションを見つけることは重要です。 しかし、一般的にNPハードである。 実現可能なMIPソリューションを探索するための有名なヒューリスティックである実現性ポンプ(FP)に触発され、DRLを用いたスマート実現性ポンプ(SFP)法を開発しました。 MIP問題の制約行列の隠蔽情報を捕捉するために,多層認識(MLP)に加えて,ポリシーネットワークのための新しい畳み込みニューラルネットワーク(CNN)構造を提案する。 さまざまな問題インスタンスの数値実験は、SFPが最初の実現可能なソリューションに到達するために必要なステップの数の観点から古典的なFPを大幅に上回っていることを示しています。 さらに、CNN構造は現在の解を入力として投影することなく動作し、FPアルゴリズムの各ステップにおける計算労力を節約して予測を求める。 これはCNN構造の表現力を強調します。

関連論文リスト

• Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
  本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。 QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。 そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
  論文  参考訳（メタデータ） (2024-06-14T10:15:03Z)
• Deep learning enhanced mixed integer optimization: Learning to reduce model dimensionality [0.0]
  この研究は、Mixed-Integer Programmingに固有の計算複雑性に対処するフレームワークを導入する。 ディープラーニングを利用することで、MIPインスタンス間の共通構造を特定し、活用する問題固有モデルを構築する。 本稿では,モデルの堅牢性と一般化性を高める合成データを生成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-17T19:15:13Z)
• Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems [5.966097889241178]
  グラフニューラルネットワーク(MPNN)は、混合整数最適化問題を高速化する。 線形最適化をエミュレートするMPNNの有効性はほとんど不明である。 線形最適化問題を解くための軽量プロキシとしてMPNNがどのように機能するかを強調した。
  論文  参考訳（メタデータ） (2023-10-16T17:31:25Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。 本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。 ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
  論文  参考訳（メタデータ） (2022-10-27T07:15:55Z)
• A Survey for Solving Mixed Integer Programming via Machine Learning [76.04988886859871]
  本稿では、混合整数(MIP)問題を解くための機械学習の動向について調査する。 本稿では、まず、MIPの定式化とプリミナリーと、MIPを解くための従来のアルゴリズムについて紹介する。 そして、機械学習とMIPアルゴリズムの異なる統合をさらに促進することを提唱する。
  論文  参考訳（メタデータ） (2022-03-06T05:03:37Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Joint Deep Reinforcement Learning and Unfolding: Beam Selection and Precoding for mmWave Multiuser MIMO with Lens Arrays [54.43962058166702]
  離散レンズアレイを用いたミリ波マルチユーザマルチインプット多重出力(MU-MIMO)システムに注目が集まっている。 本研究では、DLA を用いた mmWave MU-MIMO システムのビームプリコーディング行列の共同設計について検討する。
  論文  参考訳（メタデータ） (2021-01-05T03:55:04Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)
• Genetic Algorithm for the Weight Maximization Problem on Weighted Automata [3.0969191504482247]
  重み問題 (WMP) は、重み付き有限状態オートマトン (WFA) 上での最高重みの単語を求める問題である。 WMPの解を近似するための遺伝的アルゴリズムに基づくメタヒューリスティックを提案し,評価する。
  論文  参考訳（メタデータ） (2020-04-11T09:30:11Z)

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

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