論文の概要: Solving a Class of Cut-Generating Linear Programs via Machine Learning
- arxiv url: http://arxiv.org/abs/2310.19920v1
- Date: Mon, 30 Oct 2023 18:31:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-01 18:03:14.840589
- Title: Solving a Class of Cut-Generating Linear Programs via Machine Learning
- Title（参考訳）: 機械学習によるカット生成線形プログラムのクラス解決
- Authors: Atefeh Rajabalizadeh and Danial Davarnia
- Abstract要約: カット生成線形プログラム(CGLP)は分離オラクルとして重要な役割を担い、混合整数プログラムの可能な領域に対して有効な不等式を生成する。
分岐木と分岐木のノードでデュアルPを実行するのは、ノード候補の数と、ノードが有用な切断平面を許容する事前知識がないため、計算的に煩雑である。
本稿では,分岐木ノードで切断面を生成できるかどうかを判定する,マシンPクラスの最適値を近似する学習に基づく新しいフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cut-generating linear programs (CGLPs) play a key role as a separation oracle
to produce valid inequalities for the feasible region of mixed-integer
programs. When incorporated inside branch-and-bound, the cutting planes
obtained from CGLPs help to tighten relaxations and improve dual bounds.
However, running the CGLPs at the nodes of the branch-and-bound tree is
computationally cumbersome due to the large number of node candidates and the
lack of a priori knowledge on which nodes admit useful cutting planes. As a
result, CGLPs are often avoided at default settings of branch-and-cut
algorithms despite their potential impact on improving dual bounds. In this
paper, we propose a novel framework based on machine learning to approximate
the optimal value of a CGLP class that determines whether a cutting plane can
be generated at a node of the branch-and-bound tree. Translating the CGLP as an
indicator function of the objective function vector, we show that it can be
approximated through conventional data classification techniques. We provide a
systematic procedure to efficiently generate training data sets for the
corresponding classification problem based on the CGLP structure. We conduct
computational experiments on benchmark instances using classification methods
such as logistic regression. These results suggest that the approximate CGLP
obtained from classification can improve the solution time compared to that of
conventional cutting plane methods. Our proposed framework can be efficiently
applied to a large number of nodes in the branch-and-bound tree to identify the
best candidates for adding a cut.
- Abstract（参考訳）: カット生成線形プログラム(CGLP)は分離オラクルとして重要な役割を担い、混合整数プログラムの可能な領域の不等式を生成する。
分岐結合内に組み込むと、CGLPから得られた切断面は緩和を緩和し、二重境界を改善するのに役立つ。
しかし,分岐木および分岐木のノードでのCGLPの実行は,ノード候補の多さや,ノードが有用な切断面を許容する事前知識の欠如により,計算に煩雑である。
その結果、CGLPは、二重境界の改善に潜在的な影響があるにもかかわらず、ブランチ・アンド・カットアルゴリズムのデフォルト設定でしばしば避けられる。
本稿では,分岐木のノードで切断面を生成できるかどうかを決定するCGLPクラスの最適値を近似する機械学習に基づく新しいフレームワークを提案する。
目的関数ベクトルのインジケータ関数としてCGLPを翻訳することにより,従来のデータ分類手法により近似できることを示す。
cglp構造に基づく対応分類問題に対する学習データセットを効率的に生成するための体系的手順を提案する。
本研究ではロジスティック回帰などの分類手法を用いてベンチマークインスタンスの計算実験を行う。
これらの結果は, 従来の切削面法と比較して, 分類から得られた近似cglpが解時間を改善することを示唆する。
提案するフレームワークは分岐木内の多数のノードに効率よく適用でき、カットを追加するのに最適な候補を特定することができる。
関連論文リスト
- Understanding Gradient Boosting Classifier: Training, Prediction, and the Role of $γ_j$ [2.44755919161855]
Gradient Boosting (GBC) は、二項分類のための機械学習アルゴリズムである。
本論文は,終端ノード値の計算に焦点をあてて,トレーニングと予測のプロセスを説明する。
私たちは、読者が理解できるように、付録にステップバイステップの例を提供します。
論文 参考訳（メタデータ） (2024-10-08T02:11:35Z) - Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees [0.0]
最適二分分類木を設計するための2つのカットベース混合整数線形最適化(MILO)法を提案する。
我々のモデルは、最小限の実用不可能なサブシステム(MIS)をオンザフライで識別し、パッケージング制約の形をとる切断平面を導出する。
論文 参考訳（メタデータ） (2024-08-02T14:37:28Z) - Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。
近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。
選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
論文 参考訳（メタデータ） (2024-05-22T20:56:34Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
論文 参考訳（メタデータ） (2023-12-07T06:19:39Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - General Cutting Planes for Bound-Propagation-Based Neural Network
Verification [144.7290035694459]
任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。
MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。
本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
論文 参考訳（メタデータ） (2022-08-11T10:31:28Z) - 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) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳（メタデータ） (2021-07-27T08:48:01Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳（メタデータ） (2020-07-24T17:06:55Z) - Fine-Grained Visual Classification with Efficient End-to-end
Localization [49.9887676289364]
本稿では,エンド・ツー・エンドの設定において,分類ネットワークと融合可能な効率的なローカライゼーションモジュールを提案する。
我々は,CUB200-2011,Stanford Cars,FGVC-Aircraftの3つのベンチマークデータセット上で,新しいモデルを評価する。
論文 参考訳（メタデータ） (2020-05-11T14:07:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。