論文の概要: PUSH: a primal heuristic based on Feasibility PUmp and SHifting
- arxiv url: http://arxiv.org/abs/2208.00191v1
- Date: Sat, 30 Jul 2022 11:32:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-02 14:23:41.200884
- Title: PUSH: a primal heuristic based on Feasibility PUmp and SHifting
- Title（参考訳）: PUSH:Fasibility PUmpとSHiftingに基づく原始的ヒューリスティック
- Authors: Giorgio Grani and Corrado Coppola and Valerio Agasucci
- Abstract要約: PUSHはFasibility PumpとShiftingを組み合わせた原始的な組み合わせである。
主なアイデアは、フィージビリティポンプの丸めフェーズを、シフトリングや他の丸めの適切な適応に置き換えることである。
特に、部分解が実現可能であり、潜在的な候補に対して不可能であり、候補者なしでは不可能である場合を区別する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work describes PUSH, a primal heuristic combining Feasibility Pump and
Shifting. The main idea is to replace the rounding phase of the Feasibility
Pump with a suitable adaptation of the Shifting and other rounding heuristics.
The algorithm presents different strategies, depending on the nature of the
partial rounding obtained. In particular, we distinguish when the partial
solution is feasible, infeasible with potential candidates, and infeasible
without candidates. We used a threshold to indicate the percentage of variables
to round with our algorithm and which other to round to the nearest integer.
Most importantly, our algorithm tackles directly equality constraints without
duplicating rows. We select the parameters of our algorithm on the 19 instances
provided for the Mip Competition 2022. Finally, we compared our approach to
other start heuristics, like Simple Rounding, Rounding, Shifting, and
Feasibility Pump on the first 800 MIPLIB2017 instances ordered by the number of
non-zeros.
- Abstract（参考訳）: 本研究は、Fasibility PumpとShiftingを組み合わせた原始ヒューリスティックPUSHについて述べる。
主なアイデアは、実現性ポンプの丸めフェーズをシフトおよび他の丸めヒューリスティックの適切な適応に置き換えることである。
このアルゴリズムは、得られた部分的な丸みの性質によって異なる戦略を示す。
特に、部分解が実現可能で、潜在的な候補に対して不可能であり、候補者なしでは不可能である場合を区別する。
我々はしきい値を用いて、変数の比率をアルゴリズムで計算し、どの変数を最も近い整数に丸めるかを示しました。
最も重要なことに、我々のアルゴリズムは行を重複することなく直接平等な制約に取り組む。
マイプコンペティション2022に提供された19のインスタンス上で,アルゴリズムのパラメータを選択する。
最後に、私たちのアプローチを、非ゼロ数で順序付けられた最初の800MIPLIB2017インスタンスにおいて、Simple Rounding、 Rounding、Shifting、Feasibility Pumpといった他の開始ヒューリスティックと比較した。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-05-28T19:02:30Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Optimal design of the Barker proposal and other locally-balanced
Metropolis-Hastings algorithms [0.2148535041822524]
We study the class of first-order local- Balanced Metropolis--Hastings algorithm introduced in Livingstone & Zanella (2021)
クラス内で特定のアルゴリズムを選択するには、ユーザは、$g(t) = tg (1/t)$を満たすバランス関数 $g:mathbbR to mathbbR$と、提案のためのノイズ分布を選択する必要がある。
ベイカー提案における雑音分布の最適選択、ガウス雑音分布下でのバランス関数の最適選択、一階局所バランスアルゴリズムの最適選択を導出する。
論文 参考訳（メタデータ） (2022-01-04T13:06:50Z) - Regret Bound Balancing and Elimination for Model Selection in Bandits
and RL [34.15978290083909]
バンディットおよび強化学習問題におけるアルゴリズムの簡易モデル選択手法を提案する。
我々は、このアプローチの総後悔は、最も有効な候補者の後悔の回数が乗算的要因であることを証明します。
線形バンディットのモデル選択における最近の取り組みとは違って,我々のアプローチは,敵の環境によってコンテキスト情報が生成されるケースをカバーできるほど多用途である。
論文 参考訳（メタデータ） (2020-12-24T00:53:42Z) - Transforming Gaussian Processes With Normalizing Flows [15.886048234706633]
パラメトリックな非可逆変換を入力依存にし、解釈可能な事前知識を符号化できることを示す。
結果の推測問題に対する変分近似を導出するが、これは変分GP回帰と同じくらい高速である。
得られたアルゴリズムの計算性能と推論性能は優れており,これを様々なデータセットで示す。
論文 参考訳（メタデータ） (2020-11-03T09:52:37Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。