論文の概要: 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 Constrained Optimization with Deep Augmented Lagrangian Methods [60.94111369773497]
機械学習(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) - Primal-Dual Continual Learning: Stability and Plasticity through
Lagrange Multipliers [93.17404959573146]
制約付き最適化問題を直接実行することは可能かつ有益であることを示す。
メモリベースのメソッドでは、以前のタスクからのサンプルの小さなサブセットをリプレイバッファに格納できる。
準最適境界を導出し、様々な連続学習ベンチマークで理論的結果を実証的に相関させる。
論文 参考訳(メタデータ) (2023-09-29T21:23:27Z) - An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural
Network with Group Sparsity [13.27709100571336]
近年,グループ正規化期間を持つリーク型ReLUネットワークが広く利用されている。
定常点を決定論的に計算する手法が存在しないことを示す。
本稿では,新しいモデルを解くための不正確な拡張ラグランジアンアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-11T11:53:15Z) - Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。
制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-12T06:13:33Z) - A Stochastic Composite Augmented Lagrangian Method For Reinforcement
Learning [9.204659134755795]
深層強化学習のための線形プログラミング(LP)の定式化について検討する。
拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。
深層パラメタライズされたラグランジアン法を提案する。
論文 参考訳(メタデータ) (2021-05-20T13:08:06Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳(メタデータ) (2020-07-07T21:26:35Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳(メタデータ) (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。