論文の概要: Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization

• arxiv url: http://arxiv.org/abs/2311.03350v2
• Date: Tue, 7 Nov 2023 17:16:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 12:27:06.649678
• Title: Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization
• Title（参考訳）: 混合整数線形最適化のための可変切削平面層
• Authors: Gabriele Dragotto, Stefan Clarke, Jaime Fern\'andez Fisac, Bartolomeo Stellato
• Abstract要約: 本稿では,パラメータ混合整数線形最適化問題の一群を,入力データにいくつかの項目が存在する場合に解く問題について考察する。 我々は分割カットを生成するためのCPLの実装を提案し、いくつかのCPLを組み合わせることでパラメトリックインスタンスの繰り返しの性質を生かした微分可能なカットプレーンアルゴリズムを考案した。
• 参考スコア（独自算出の注目度）: 1.7398512809572197
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We consider the problem of solving a family of parametric mixed-integer linear optimization problems where some entries in the input data change. We introduce the concept of cutting-plane layer (CPL), i.e., a differentiable cutting-plane generator mapping the problem data and previous iterates to cutting planes. We propose a CPL implementation to generate split cuts, and by combining several CPLs, we devise a differentiable cutting-plane algorithm that exploits the repeated nature of parametric instances. In an offline phase, we train our algorithm by updating the internal parameters controlling the CPLs, thus altering cut generation. Once trained, our algorithm computes, with predictable execution times and a fixed number of cuts, solutions with low integrality gaps. Preliminary computational tests show that our algorithm generalizes on unseen instances and captures underlying parametric structures.
• Abstract（参考訳）: 入力データの一部が変化するパラメトリック混合整数線形最適化問題の一群を解決する問題を考える。 本稿では,切削平面層(CPL)の概念,すなわち,問題データと過去の繰り返しを切断平面にマッピングする識別可能な切削平面発生器を紹介する。 我々は分割カットを生成するためのCPLの実装を提案し、いくつかのCPLを組み合わせることでパラメトリックインスタンスの繰り返しの性質を生かした微分可能なカットプレーンアルゴリズムを考案した。 オフラインフェーズでは、CPLを制御する内部パラメータを更新し、カット生成を変更することでアルゴリズムを訓練する。 一度トレーニングすると、アルゴリズムは、予測可能な実行時間と一定数のカット、低い積分ギャップの解を計算します。 予備計算実験により,本アルゴリズムは未知のインスタンスを一般化し,基礎となるパラメトリック構造を捉える。

関連論文リスト

• Learning to Remove Cuts in Integer Linear Programming [57.15699051569638]
  本研究では, 学習可能なパラメトリック基準の下で, 手法の前回の繰り返しで導入された前回のカットの除去について検討する。 基本的な最適化設定では、カット削除ポリシーは、ヒューマンベースおよび機械学習誘導のカット追加ポリシーよりも大幅に改善される可能性があることを実証する。
  論文  参考訳（メタデータ） (2024-06-26T22:50:43Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
  データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。 提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。 本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
  論文  参考訳（メタデータ） (2022-04-07T17:27:18Z)
• Accelerated nonlinear primal-dual hybrid gradient algorithms with applications to machine learning [0.0]
  原始双対ハイブリッド勾配(PDHG)は、サドル点構造を持つ凸最適化問題をより小さなサブプロブレムに分割する一階法である。 PDHGは、手前の問題に対して微調整されたステップサイズパラメータを必要とする。 我々は,機械学習に関連する幅広い最適化問題に対して,PDHGアルゴリズムの高速化された非線形変種を導入する。
  論文  参考訳（メタデータ） (2021-09-24T22:37:10Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Stochastic Cutting Planes for Data-Driven Optimization [6.243995448840211]
  我々は、アルゴリズムが高い確率で$epsilon$optimalソリューションに収束することができることを示しています。 我々は, 切削面のサンプリング限界を実験的に検討し, 多くの問題に対して, 高品質な解には, サンプリングサイズ$o(sqrt[3]n)$ が十分であることを示す。
  論文  参考訳（メタデータ） (2021-03-03T16:21:32Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)

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

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