論文の概要: Learning Cut Generating Functions for Integer Programming

• arxiv url: http://arxiv.org/abs/2405.13992v1
• Date: Wed, 22 May 2024 20:56:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-24 20:04:17.238602
• Title: Learning Cut Generating Functions for Integer Programming
• Title（参考訳）: 整数プログラミングのためのカット生成関数の学習
• Authors: Hongyu Cheng, Amitabh Basu,
• Abstract要約: 分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。 近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。 選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
• 参考スコア（独自算出の注目度）: 1.1510009152620668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems in practice. A key ingredient of branch-and-cut is the use of cutting planes which are derived constraints that reduce the search space for an optimal solution. Selecting effective cutting planes to produce small branch-and-cut trees is a critical challenge in the branch-and-cut algorithm. Recent advances have employed a data-driven approach to select optimal cutting planes from a parameterized family, aimed at reducing the branch-and-bound tree size (in expectation) for a given distribution of integer programming instances. We extend this idea to the selection of the best cut generating function (CGF), which is a tool in the integer programming literature for generating a wide variety of cutting planes that generalize the well-known Gomory Mixed-Integer (GMI) cutting planes. We provide rigorous sample complexity bounds for the selection of an effective CGF from certain parameterized families that provably performs well for any specified distribution on the problem instances. Our empirical results show that the selected CGF can outperform the GMI cuts for certain distributions. Additionally, we explore the sample complexity of using neural networks for instance-dependent CGF selection.
• Abstract（参考訳）: 分岐とカットのアルゴリズムは、実際に大規模な整数プログラミング問題を解く方法である。 分岐切断の鍵となる要素は、最適解の探索空間を減少させる導出制約である切断平面を使用することである。 小さな枝切り木を生成するために効率的な切削平面を選択することは、枝切りアルゴリズムにおいて重要な課題である。 近年の進歩は、パラメータ化されたファミリーから最適な切断平面を選択するためのデータ駆動型アプローチを採用しており、整数プログラミングインスタンスの所定の分布に対する分岐とバウンドのツリーサイズ(期待通り)を減らすことを目的としている。 我々はこのアイデアを、よく知られたGomory Mixed-Integer(GMI)切断平面を一般化する多種多様な切断平面を生成するための整数プログラミング文献におけるツールであるベストカット生成関数(CGF)の選択に拡張する。 問題インスタンス上の特定の分布に対して良好に動作するパラメータ化された族から有効なCGFを選択するための厳密なサンプル複雑性境界を提供する。 実験の結果,選択したCGFは特定の分布に対するGMIカットよりも優れていた。 さらに、ニューラルネットワークをインスタンス依存のCGF選択に使用する際の、サンプルの複雑さについても検討する。

関連論文リスト

• Random Aggregate Beamforming for Over-the-Air Federated Learning in Large-Scale Networks [66.18765335695414]
  本稿では,アグリゲーションエラーを最小限に抑え,選択したデバイス数を最大化する目的で,共同装置の選択とアグリゲーションビームフォーミング設計について検討する。 コスト効率のよい方法でこの問題に取り組むために,ランダムな集合ビームフォーミング方式を提案する。 また, 得られた集計誤差と, デバイス数が大きい場合に選択したデバイス数についても解析を行った。
  論文  参考訳（メタデータ） (2024-02-20T23:59:45Z)
• Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization [1.7398512809572197]
  本稿では,パラメータ混合整数線形最適化問題の一群を,入力データにいくつかの項目が存在する場合に解く問題について考察する。 我々は分割カットを生成するためのCPLの実装を提案し、いくつかのCPLを組み合わせることでパラメトリックインスタンスの繰り返しの性質を生かした微分可能なカットプレーンアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2023-11-06T18:57:07Z)
• Solving a Class of Cut-Generating Linear Programs via Machine Learning [0.0]
  カット生成線形プログラム(CGLP)は分離オラクルとして重要な役割を担い、混合整数プログラムの可能な領域に対して有効な不等式を生成する。 分岐木と分岐木のノードでデュアルPを実行するのは、ノード候補の数と、ノードが有用な切断平面を許容する事前知識がないため、計算的に煩雑である。 本稿では,分岐木ノードで切断面を生成できるかどうかを判定する,マシンPクラスの最適値を近似する学習に基づく新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-30T18:31:52Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。 MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。 本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
  論文  参考訳（メタデータ） (2022-08-11T10:31:28Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• Adaptive Cut Selection in Mixed-Integer Linear Programming [0.294944680995069]
  カットセレクション(英: cut selection)は、現代の全ての混合整数線形計画解法で用いられるサブルーチンである。 混合整数線形プログラムのファミリーを、無限に多くのファミリーワイド有効なカットと共に提示する。 特定のカット選択規則について、パラメータ空間の有限グリッド探索は常に全てのパラメータ値を見逃すことを示す。
  論文  参考訳（メタデータ） (2022-02-22T15:07:33Z)
• Improved Learning Bounds for Branch-and-Cut [98.92725321081994]
  分岐とカットは整数プログラムの解法として最も広く使われているアルゴリズムである。 ますます人気のあるアプローチは、機械学習を使ってパラメータをチューニングすることだ。 本稿では,本手法のサンプル保証について述べる。
  論文  参考訳（メタデータ） (2021-11-18T04:07:29Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)

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

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