論文の概要: Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs

• arxiv url: http://arxiv.org/abs/2310.14659v2
• Date: Fri, 18 Oct 2024 11:32:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-21 14:21:56.395783
• Title: Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs
• Title（参考訳）: 混合整数線形プログラムに対する正確なラグランジアン乗算器の予測
• Authors: Francesco Demelas, Joseph Le Roux, Mathieu Lacroix, Axel Parmentier,
• Abstract要約: 我々は、降下を回避し、局所的な最適化を効果的に減らし、深層学習アプローチを導入する。 提案手法は, 連続緩和とラグランジアン境界とのギャップの最大85%を解消し, 降下に基づくラグランジアン法において, 高品質なウォームスタートを提供することを示す。
• 参考スコア（独自算出の注目度）: 2.6899003881035406
• License:
• Abstract: Lagrangian relaxation stands among the most efficient approaches for solving a Mixed Integer Linear Programs (MILP) with difficult constraints. Given any duals for these constraints, called Lagrangian Multipliers (LMs), it returns a bound on the optimal value of the MILP, and Lagrangian methods seek the LMs giving the best such bound. But these methods generally rely on iterative algorithms resembling gradient descent to maximize the concave piecewise linear dual function: the computational burden grows quickly with the number of relaxed constraints. We introduce a deep learning approach that bypasses the descent, effectively amortizing the local, per instance, optimization. A probabilistic encoder based on a graph convolutional network computes high-dimensional representations of relaxed constraints in MILP instances. A decoder then turns these representations into LMs. We train the encoder and decoder jointly by directly optimizing the bound obtained from the predicted multipliers. Numerical experiments show that our approach closes up to 85~\% of the gap between the continuous relaxation and the best Lagrangian bound, and provides a high quality warm-start for descent based Lagrangian methods.
• Abstract（参考訳）: ラグランジアン緩和は、難しい制約でMILP(Mixed Integer Linear Programs)を解く最も効率的な方法の一つである。 ラグランジアン乗数 (LM) と呼ばれるこれらの制約の双対が与えられたとき、それはMILPの最適値の有界を返し、ラグランジアン法は最高の有界を与える LM を求める。 しかし、これらの手法は一般に勾配降下に類似した反復アルゴリズムに頼り、凹凸の線形双対関数を最大化する: 計算の重みは緩和された制約の数とともに急速に増加する。 我々は、降下を回避し、局所的な最適化を効果的に減らし、深層学習アプローチを導入する。 グラフ畳み込みネットワークに基づく確率エンコーダは、MILPインスタンスにおける緩和制約の高次元表現を計算する。 デコーダはこれらの表現をLMに変換する。 我々は、予測乗算器から得られる境界を直接最適化することにより、エンコーダとデコーダを共同で訓練する。 数値実験により, 連続緩和と最良ラグランジアン境界とのギャップの最大85~\%が閉鎖され, 降下に基づくラグランジアン法において, 高品質なウォームスタートが提供されることがわかった。

関連論文リスト

• Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning [2.8425837800129696]
  ラグランジアン分解(LD)は、制約付き最適化問題に対して二重境界を与える緩和法である。 この研究は、制約プログラミングにおいて有効な双対境界を学習するための最初の一般的な方法を示す。
  論文  参考訳（メタデータ） (2024-08-22T19:26:29Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• Learning Lagrangian Multipliers for the Travelling Salesman Problem [12.968608204035611]
  本稿では,グラフニューラルネットワークの能力を活用して問題構造を利用する,革新的な教師なし学習手法を提案する。 この手法を、旅行セールスマン問題に対する有名なヘルド・カルプ・ラグランジアン緩和に適用する。 実現可能な解を見つけることに焦点を当てた既存の文献の多くとは対照的に、我々のアプローチは両面で動作し、学習が最適性の証明を加速できることを示す。
  論文  参考訳（メタデータ） (2023-12-22T17:09:34Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle [16.290192687098383]
  本稿では,アフィン制約を伴う凸複合最適化問題について考察する。 正確なプロジェクション/近距離計算が難解な高次元アプリケーションにより,テキスト投影のないラグランジアン型拡張手法を提案する。
  論文  参考訳（メタデータ） (2022-10-25T12:51:43Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  深層強化学習のための線形プログラミング(LP)の定式化について検討する。 拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。 深層パラメタライズされたラグランジアン法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T13:08:06Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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