論文の概要: Learning to Remove Cuts in Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2406.18781v1
• Date: Wed, 26 Jun 2024 22:50:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-28 15:47:01.267308
• Title: Learning to Remove Cuts in Integer Linear Programming
• Title（参考訳）: 整数線形プログラミングにおけるカット除去の学習
• Authors: Pol Puigdemont, Stratis Skoulakis, Grigorios Chrysos, Volkan Cevher,
• Abstract要約: 本研究では, 学習可能なパラメトリック基準の下で, 手法の前回の繰り返しで導入された前回のカットの除去について検討する。 基本的な最適化設定では、カット削除ポリシーは、ヒューマンベースおよび機械学習誘導のカット追加ポリシーよりも大幅に改善される可能性があることを実証する。
• 参考スコア（独自算出の注目度）: 57.15699051569638
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional optimal solution while not affecting the optimal integer solution. In this work, we explore a novel approach within cutting plane methods: instead of only adding new cuts, we also consider the removal of previous cuts introduced at any of the preceding iterations of the method under a learnable parametric criteria. We demonstrate that in fundamental combinatorial optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies even when implemented with simple models.
• Abstract（参考訳）: カット平面法は整数線形プログラム(ILP)を解くための基本的な手法である。 このような手法の各反復において、最適整数解に影響を与えることなく、前の分数的最適解を除外する目的で、制約セットに追加線形制約(カット)が導入される。 そこで本研究では,新しいカットを付加する代わりに,学習可能なパラメトリック基準の下で,前回の反復で導入したカットの除去についても検討する。 基本組合せ最適化設定において、カット削除ポリシーは、単純なモデルで実装しても、人間ベースおよび機械学習誘導のカット追加ポリシーよりも大幅に改善されることを示した。

関連論文リスト

• Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model [6.123324869194196]
  混合ロジット顧客選択モデルに基づくアソシエーション最適化問題について検討する。 既存の正確な手法は、主にMILP (mixed-integer linear programming) やCONIC (Second-order cone) の修正に依存している。 我々の研究は、単調に超モジュラーかつ凸であることを示す客観的関数の成分に焦点をあてることによって、この問題に対処する。
  論文  参考訳（メタデータ） (2024-07-26T06:27:11Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2024-02-24T09:47:46Z)
• Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization [1.7398512809572197]
  本稿では,パラメータ混合整数線形最適化問題の一群を,入力データにいくつかの項目が存在する場合に解く問題について考察する。 我々は分割カットを生成するためのCPLの実装を提案し、いくつかのCPLを組み合わせることでパラメトリックインスタンスの繰り返しの性質を生かした微分可能なカットプレーンアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2023-11-06T18:57:07Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Cutting Plane Selection with Analytic Centers and Multiregression [2.8757106397019228]
  緩和可能な集合の関連部分を分離する程度を定量化することにより、カットの値を評価するための新しい距離ベースの尺度を提案する。 距離測定の選択が根ノード性能および枝・枝木全体に与える影響を評価する。 解析中心に基づく手法は,探索空間の探索に必要な分岐ノードの数を大幅に削減できることを示す。
  論文  参考訳（メタデータ） (2022-12-14T14:06:27Z)
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。 本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
  論文  参考訳（メタデータ） (2022-06-27T16:07:27Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  複数変数の非プロブレムに挑戦する新しい解を提案する。 提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
  論文  参考訳（メタデータ） (2020-09-09T10:45:00Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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