論文の概要: Cutting Plane Selection with Analytic Centers and Multiregression
- arxiv url: http://arxiv.org/abs/2212.07231v1
- Date: Wed, 14 Dec 2022 14:06:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-15 17:54:20.105033
- Title: Cutting Plane Selection with Analytic Centers and Multiregression
- Title（参考訳）: 解析中心と多回帰による切削平面選択
- Authors: Mark Turner, Timo Berthold, Mathieu Besan\c{c}on, Thorsten Koch
- Abstract要約: 緩和可能な集合の関連部分を分離する程度を定量化することにより、カットの値を評価するための新しい距離ベースの尺度を提案する。
距離測定の選択が根ノード性能および枝・枝木全体に与える影響を評価する。
解析中心に基づく手法は,探索空間の探索に必要な分岐ノードの数を大幅に削減できることを示す。
- 参考スコア（独自算出の注目度）: 2.8757106397019228
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cutting planes are a crucial component of state-of-the-art mixed-integer
programming solvers, with the choice of which subset of cuts to add being vital
for solver performance. We propose new distance-based measures to qualify the
value of a cut by quantifying the extent to which it separates relevant parts
of the relaxed feasible set. For this purpose, we use the analytic centers of
the relaxation polytope or of its optimal face, as well as alternative optimal
solutions of the linear programming relaxation. We assess the impact of the
choice of distance measure on root node performance and throughout the whole
branch-and-bound tree, comparing our measures against those prevalent in the
literature. Finally, by a multi-output regression, we predict the relative
performance of each measure, using static features readily available before the
separation process. Our results indicate that analytic center-based methods
help to significantly reduce the number of branch-and-bound nodes needed to
explore the search space and that our multiregression approach can further
improve on any individual method.
- Abstract（参考訳）: カットプレーンは最先端の混合整数型プログラミング解法の重要な構成要素であり、解法のパフォーマンスに不可欠なカットのサブセットを選択する。
緩和可能な集合の関連部分を分離する程度を定量化することにより、カットの値を評価するための新しい距離ベースの尺度を提案する。
この目的のために、我々は、リニアプログラミング緩和の代替の最適解と同様に、緩和ポリトープまたはその最適面の解析的中心を用いる。
そこで本研究では,本論文で広く普及しているものと比較し,距離尺度の選択が根ノード性能および分枝木全体に与える影響を評価した。
最後に,マルチアウトプット回帰により,分離処理前に容易に利用可能な静的特徴を用いて,各指標の相対的性能を予測する。
解析中心に基づく手法は,探索空間を探索するために必要な分岐ノードの数を大幅に削減し,多回帰手法により各手法をさらに改善できることが示唆された。
関連論文リスト
- Learning to Remove Cuts in Integer Linear Programming [57.15699051569638]
本研究では, 学習可能なパラメトリック基準の下で, 手法の前回の繰り返しで導入された前回のカットの除去について検討する。
基本的な最適化設定では、カット削除ポリシーは、ヒューマンベースおよび機械学習誘導のカット追加ポリシーよりも大幅に改善される可能性があることを実証する。
論文 参考訳（メタデータ） (2024-06-26T22:50:43Z) - Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
オンライン報酬指標の偏りのないオフライン推定を最適化する意思決定ポリシーを学習することを目指している。
学習シナリオにおける同値性に基づく単一のフレームワークを提案する。
我々のフレームワークは、分散最適非バイアス推定器の特徴付けを可能にし、それに対する閉形式解を提供する。
論文 参考訳（メタデータ） (2024-05-09T12:52:22Z) - Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - Approximation of a Pareto Set Segment Using a Linear Model with Sharing Variables [14.161627541155775]
最適性と変数共有を両立させる性能指標を開発した。
次に、ユーザの要求を満たすためのメトリックを最小限に抑えるモデルを見つけるアルゴリズムを設計する。
実験結果から,選好ベクトルから局所領域の解への写像を近似した線形モデルが得られることが示された。
論文 参考訳（メタデータ） (2024-03-30T05:42:07Z) - Exploiting Temporal Structures of Cyclostationary Signals for
Data-Driven Single-Channel Source Separation [98.95383921866096]
単一チャネルソース分離(SCSS)の問題点について検討する。
我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。
本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
論文 参考訳（メタデータ） (2022-08-22T14:04:56Z) - Parallel feature selection based on the trace ratio criterion [4.30274561163157]
本研究は,PFSTを用いた並列特徴選択という,新しい並列特徴選択手法を提案する。
提案手法は,Fisher's Discriminant Analysisで用いられるクラス分離性の尺度であるトレース基準を用いて特徴的有用性を評価する。
実験により,本手法は,比較対象の他の手法による時間的差のごく一部で,少数の特徴セットを生成できることが確認された。
論文 参考訳（メタデータ） (2022-03-03T10:50:33Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2021-09-23T17:38:24Z) - Piecewise linear regression and classification [0.20305676256390928]
本稿では,線形予測器を用いた多変量回帰と分類問題の解法を提案する。
本論文で記述されたアルゴリズムのpython実装は、http://cse.lab.imtlucca.it/bemporad/parcで利用可能である。
論文 参考訳（メタデータ） (2021-03-10T17:07:57Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳（メタデータ） (2020-08-17T16:56:06Z) - How to choose the most appropriate centrality measure? A decision tree approach [0.0]
簡単なグラフ上での集中度挙動の専門的な概念に依拠したカリング法を導入する。
このアプローチを、新しいカーネルベースの指標を含む40の中央集権の多様な集合に適用する。
カルリング法を適用することで、いくつかの中心性指標に関する洞察に富んだ知見が得られる。
論文 参考訳（メタデータ） (2020-03-02T17:38:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。