論文の概要: Cutting Plane Selection with Analytic Centers and Multiregression
- arxiv url: http://arxiv.org/abs/2212.07231v2
- Date: Thu, 15 Dec 2022 21:58:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-19 16:25:39.665321
- 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(参考訳): カットプレーンは最先端の混合整数型プログラミング解法の重要な構成要素であり、解法のパフォーマンスに不可欠なカットのサブセットを選択する。
緩和可能な集合の関連部分を分離する程度を定量化することにより、カットの値を評価するための新しい距離ベースの尺度を提案する。
この目的のために、我々は、リニアプログラミング緩和の代替の最適解と同様に、緩和ポリトープまたはその最適面の解析的中心を用いる。
そこで本研究では,本論文で広く普及しているものと比較し,距離尺度の選択が根ノード性能および分枝木全体に与える影響を評価した。
最後に,マルチアウトプット回帰により,分離処理前に容易に利用可能な静的特徴を用いて,各指標の相対的性能を予測する。
解析中心に基づく手法は,探索空間を探索するために必要な分岐ノードの数を大幅に削減し,多回帰手法により各手法をさらに改善できることが示唆された。
関連論文リスト
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳(メタデータ) (2022-09-16T19:15:50Z) - Exploiting Temporal Structures of Cyclostationary Signals for
Data-Driven Single-Channel Source Separation [98.95383921866096]
単一チャネルソース分離(SCSS)の問題点について検討する。
我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。
本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
論文 参考訳(メタデータ) (2022-08-22T14:04:56Z) - Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees
with Continuous Features [5.663538370244174]
本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。
提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
論文 参考訳(メタデータ) (2022-06-23T17:19:29Z) - Reinforcement Learning with a Terminator [80.34572413850186]
我々は, TerMDP のパラメータを学習し, 推定問題の構造を活用し, 状態ワイドな信頼境界を提供する。
我々はこれらを用いて証明可能な効率のよいアルゴリズムを構築し、終端を考慮し、その後悔を抑える。
論文 参考訳(メタデータ) (2022-05-30T18:40:28Z) - 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) - Data-Driven Combinatorial Optimization with Incomplete Information: a
Distributionally Robust Optimization Approach [0.0]
我々は,コストベクトルが先行性を持たないが,有限データセットでしか観測できない線形最適化問題を解析する。
目標は、データセットを対象関数の期待値の推定値に変換する手順を見つけることである。
論文 参考訳(メタデータ) (2021-05-28T23:17:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。