論文の概要: Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning
- arxiv url: http://arxiv.org/abs/2408.12695v1
- Date: Thu, 22 Aug 2024 19:26:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-26 16:38:31.652117
- Title: Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning
- Title（参考訳）: 制約プログラミングにおける有意な双対境界の学習:自己監督型学習によるラグランジアン分解の促進
- Authors: Swann Bessa, Darius Dabert, Max Bourgeat, Louis-Martin Rousseau, Quentin Cappart,
- Abstract要約: ラグランジアン分解(LD)は、制約付き最適化問題に対して二重境界を与える緩和法である。
この研究は、制約プログラミングにおいて有効な双対境界を学習するための最初の一般的な方法を示す。
- 参考スコア（独自算出の注目度）: 2.8425837800129696
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Lagrangian decomposition (LD) is a relaxation method that provides a dual bound for constrained optimization problems by decomposing them into more manageable sub-problems. This bound can be used in branch-and-bound algorithms to prune the search space effectively. In brief, a vector of Lagrangian multipliers is associated with each sub-problem, and an iterative procedure (e.g., a sub-gradient optimization) adjusts these multipliers to find the tightest bound. Initially applied to integer programming, Lagrangian decomposition also had success in constraint programming due to its versatility and the fact that global constraints provide natural sub-problems. However, the non-linear and combinatorial nature of sub-problems in constraint programming makes it computationally intensive to optimize the Lagrangian multipliers with sub-gradient methods at each node of the tree search. This currently limits the practicality of LD as a general bounding mechanism for constraint programming. To address this challenge, we propose a self-supervised learning approach that leverages neural networks to generate multipliers directly, yielding tight bounds. This approach significantly reduces the number of sub-gradient optimization steps required, enhancing the pruning efficiency and reducing the execution time of constraint programming solvers. This contribution is one of the few that leverage learning to enhance bounding mechanisms on the dual side, a critical element in the design of combinatorial solvers. To our knowledge, this work presents the first generic method for learning valid dual bounds in constraint programming.
- Abstract（参考訳）: ラグランジアン分解(LD)は、より管理可能なサブプロブレムに分解することで、制約付き最適化問題の二重境界を提供する緩和法である。
このバウンダリは、分岐とバウンダリのアルゴリズムで検索空間を効果的にプルークするために使用することができる。
簡単に言えば、ラグランジュ乗算のベクトルは各部分確率に関連付けられ、反復手順(例えば、部分次最適化)はこれらの乗算を調整して最も厳密な境界を求める。
当初、整数プログラミングに適用されたラグランジアン分解は、その汎用性と大域的制約が自然なサブプロブレムを提供するという事実により、制約プログラミングにも成功した。
しかし、制約プログラミングにおけるサブプロブレムの非線形および組合せ的性質は、木探索の各ノードにおける下位次法を用いてラグランジアン乗算器を最適化する計算集約性をもたらす。
これは、制約プログラミングの一般的なバウンディングメカニズムとしてのLDの実用性を制限している。
この課題に対処するために,ニューラルネットワークを利用して直接乗算器を生成する自己教師付き学習手法を提案する。
このアプローチは、必要となる下位段階の最適化ステップの数を大幅に削減し、プルーニング効率を向上し、制約プログラミングソルバの実行時間を短縮する。
この貢献は、組合せ解法の設計において重要な要素である双対側の境界機構の強化に学習を活用する数少ない要素の1つである。
我々の知る限り、この研究は制約プログラミングにおいて有効な双対境界を学習するための最初の一般的な方法である。
関連論文リスト
- A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints [4.6796315389639815]
分散最適化問題は分散制約の存在下では解決できない。
目的関数の勾配と制約写像のヤコビアンを同時に追跡する新しいアルゴリズムを導入する。
合成と実世界の両方のデータセットに数値的な結果を示す。
論文 参考訳（メタデータ） (2024-09-08T06:57:35Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Constrained Bi-Level Optimization: Proximal Lagrangian Value function
Approach and Hessian-free Algorithm [8.479947546216131]
We developed a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA)
LV-HBAは特に機械学習アプリケーションに適している。
論文 参考訳（メタデータ） (2024-01-29T13:50:56Z) - Learning Lagrangian Multipliers for the Travelling Salesman Problem [12.968608204035611]
本稿では,グラフニューラルネットワークの能力を活用して問題構造を利用する,革新的な教師なし学習手法を提案する。
この手法を、旅行セールスマン問題に対する有名なヘルド・カルプ・ラグランジアン緩和に適用する。
実現可能な解を見つけることに焦点を当てた既存の文献の多くとは対照的に、我々のアプローチは両面で動作し、学習が最適性の証明を加速できることを示す。
論文 参考訳（メタデータ） (2023-12-22T17:09:34Z) - Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs [2.6899003881035406]
我々は、降下を回避し、局所的な最適化を効果的に減らし、深層学習アプローチを導入する。
提案手法は, 連続緩和とラグランジアン境界とのギャップの最大85%を解消し, 降下に基づくラグランジアン法において, 高品質なウォームスタートを提供することを示す。
論文 参考訳（メタデータ） (2023-10-23T07:53:47Z) - Optimization-based Block Coordinate Gradient Coding for Mitigating
Partial Stragglers in Distributed Learning [58.91954425047425]
本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。
L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
論文 参考訳（メタデータ） (2022-06-06T09:25:40Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - A Stochastic Composite Augmented Lagrangian Method For Reinforcement
Learning [9.204659134755795]
深層強化学習のための線形プログラミング(LP)の定式化について検討する。
拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。
深層パラメタライズされたラグランジアン法を提案する。
論文 参考訳（メタデータ） (2021-05-20T13:08:06Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。