論文の概要: Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework

• arxiv url: http://arxiv.org/abs/2312.03413v1
• Date: Wed, 6 Dec 2023 10:50:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-07 15:07:22.908340
• Title: Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework
• Title（参考訳）: ラグランジュ双対フレームワークを用いたナップサック問題の近似解
• Authors: Mitchell Keegan and Mahdi Abolghasemi
• Abstract要約: ラグランジアンデュアルフレームワークを用いて,クナプサック問題の解を近似するニューラルネットワークモデルを開発した。 我々は,ベースラインニューラルネットワークと比較して,最適性をわずかに低減した強い制約満足度を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Knapsack Problem is a classic problem in combinatorial optimisation. Solving these problems may be computationally expensive. Recent years have seen a growing interest in the use of deep learning methods to approximate the solutions to such problems. A core problem is how to enforce or encourage constraint satisfaction in predicted solutions. A promising approach for predicting solutions to constrained optimisation problems is the Lagrangian Dual Framework which builds on the method of Lagrangian Relaxation. In this paper we develop neural network models to approximate Knapsack Problem solutions using the Lagrangian Dual Framework while improving constraint satisfaction. We explore the problems of output interpretation and model selection within this context. Experimental results show strong constraint satisfaction with a minor reduction of optimality as compared to a baseline neural network which does not explicitly model the constraints.
• Abstract（参考訳）: クナプサック問題は組合せ最適化における古典的な問題である。 これらの問題を解決するには計算コストがかかる。 近年,このような問題の解を近似する深層学習手法への関心が高まっている。 中心的な問題は、予測されたソリューションにおける制約満足度をどのように強制するか、あるいは促進するかである。 制約付き最適化問題に対する解決策を予測するための有望なアプローチは、ラグランジアン緩和法に基づくラグランジアンデュアルフレームワークである。 本稿では,制約満足度を改善しつつ,ラグランジアンデュアルフレームワークを用いてクナプサック問題の解を近似するニューラルネットワークモデルを開発する。 この文脈における出力解釈とモデル選択の問題について検討する。 実験結果は,制約を明示的にモデル化しないベースラインニューラルネットワークと比較して,最適性をわずかに低下させる強い制約満足度を示す。

関連論文リスト

• Learning to Optimize for Mixed-Integer Non-linear Programming [20.469394148261838]
  混合整数非NLPプログラム(MINLP)はエネルギーシステムや輸送など様々な領域で発生するが、解決は困難である。 機械学習の最近の進歩は、最適化のための学習として知られる領域において、顕著な成功をもたらしている。 勾配を保ちながら整数出力を生成する2つの異なる補正層を提案する。
  論文  参考訳（メタデータ） (2024-10-14T20:14:39Z)
• WANCO: Weak Adversarial Networks for Constrained Optimization problems [5.257895611010853]
  まず、拡張ラグランジアン法を用いてミニマックス問題をミニマックス問題に変換する。 次に、それぞれ原始変数と双対変数を表すために、2つの(または複数の)ディープニューラルネットワークを使用します。 ニューラルネットワークのパラメータは、敵のプロセスによって訓練される。
  論文  参考訳（メタデータ） (2024-07-04T05:37:48Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• 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)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
  本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。 制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-12T06:13:33Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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