論文の概要: Solving the Batch Stochastic Bin Packing Problem in Cloud: A
Chance-constrained Optimization Approach
- arxiv url: http://arxiv.org/abs/2207.11122v1
- Date: Wed, 20 Jul 2022 08:34:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-25 13:31:57.615711
- Title: Solving the Batch Stochastic Bin Packing Problem in Cloud: A
Chance-constrained Optimization Approach
- Title（参考訳）: クラウドにおけるバッチ確率ビンパッキング問題を解決する - 確率的最適化アプローチ
- Authors: Jie Yan, Yunlei Lu, Liting Chen, Si Qin, Yixin Fang, Qingwei Lin,
Thomas Moscibroda, Saravan Rajmohan and Dongmei Zhang
- Abstract要約: 本稿では,第1のクラウドにおける重要な資源配分問題について検討する。
数十のサービスがあり、各サービスは動的リソース使用量でコンテナのセットを実行します。
生成的アプローチでコンテナリソース利用分布をモデル化することにより,同質なデータセットでUCaCを近似できることを明らかにする。
- 参考スコア（独自算出の注目度）: 32.124999915256325
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper investigates a critical resource allocation problem in the first
party cloud: scheduling containers to machines. There are tens of services and
each service runs a set of homogeneous containers with dynamic resource usage;
containers of a service are scheduled daily in a batch fashion. This problem
can be naturally formulated as Stochastic Bin Packing Problem (SBPP). However,
traditional SBPP research often focuses on cases of empty machines, whose
objective, i.e., to minimize the number of used machines, is not well-defined
for the more common reality with nonempty machines. This paper aims to close
this gap. First, we define a new objective metric, Used Capacity at Confidence
(UCaC), which measures the maximum used resources at a probability and is
proved to be consistent for both empty and nonempty machines, and reformulate
the SBPP under chance constraints. Second, by modeling the container resource
usage distribution in a generative approach, we reveal that UCaC can be
approximated with Gaussian, which is verified by trace data of real-world
applications. Third, we propose an exact solver by solving the equivalent
cutting stock variant as well as two heuristics-based solvers -- UCaC best fit,
bi-level heuristics. We experimentally evaluate these solvers on both synthetic
datasets and real application traces, demonstrating our methodology's advantage
over traditional SBPP optimal solver minimizing the number of used machines,
with a low rate of resource violations.
- Abstract（参考訳）: 本稿では,コンテナをマシンにスケジューリングするファーストパーティクラウドにおける重要なリソース割り当て問題について検討する。
サービスには数十のサービスがあり、各サービスは動的リソース使用量で一組の均一なコンテナを実行する。
この問題はSBPP(Stochastic Bin Packing Problem)として自然に定式化できる。
しかしながら、従来のSBPP研究は、空の機械の場合、すなわち使用機械の数を最小化する目的が、空でない機械とのより一般的な現実に対して十分に定義されていないことに焦点を当てることが多い。
本稿は,このギャップを埋めることを目的とする。
まず, 最大使用資源を確率で測定し, 空機と空機と空機の両方に一貫性があることを証明し, sbppを偶然の制約下で再構成する, 新たな客観的指標, ucac(compact capacity at confidence)を定義した。
第2に,生成的アプローチでコンテナリソースの利用分布をモデル化することにより,実世界のアプリケーションのトレースデータによって検証されるgaussianを用いてucacを近似できることを明らかにする。
第3に,等価なカットストック変種と2つのヒューリスティックスに基づく解法であるucac best fit,bi-level heuristicsを解くことで,正確な解法を提案する。
我々は,これらの解法を,合成データセットと実アプリケーショントレースの両方で実験的に評価し,従来のSBPP最適解法と比較して,リソース違反の少ない使用機数を最小化する手法の利点を実証した。
関連論文リスト
- A Federated Distributionally Robust Support Vector Machine with Mixture of Wasserstein Balls Ambiguity Set for Distributed Fault Diagnosis [3.662364375995991]
本研究では、中央サーバとG$クライアントで構成されるネットワーク上で、データを共有せずに、分散ロバストな(DR)サポートベクタマシン(SVM)をフェデレーション方式でトレーニングする問題について検討する。
グローバルFDR-SVMをトレーニングするための2つの分散最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-04T19:21:45Z) - Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
大規模データの爆発はシングルマシンシステムの処理能力を上回っている。
分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。
そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-30T13:22:08Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
本稿では,Wasserstein Barycenter問題を解くための新しいスケーラブルなアプローチを提案する。
我々の手法は最近のNeural OTソルバをベースとしている。
また,提案手法の理論的誤差境界も確立する。
論文 参考訳（メタデータ） (2024-02-06T09:17:07Z) - Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
半/ライブラリベースのアンミックスのための新しい凸凸モデルを提案する。
スパース・アンミキシングの代替手法の有効性を実証する。
論文 参考訳（メタデータ） (2024-01-23T10:07:41Z) - Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms,
and Applications [38.98556852157875]
ランダムな重みの確率分布が未知であるがサンプルデータのみが利用可能であるCCMCKPの実践シナリオに注目した。
CCMCKPを解決するために,データ駆動型適応局所探索(DDALS)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-26T13:35:05Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳（メタデータ） (2023-05-29T17:25:26Z) - Optimal Resource Allocation for Serverless Queries [8.59568779761598]
以前の作業では、リソース割り当てと実行時の積極的なトレードオフを無視しながら、ピークアロケーションの予測に重点を置いていた。
本稿では,新しいクエリと過去のクエリの両方に対して,アグレッシブなトレードオフでパフォーマンスを予測できる最適なリソース割り当てシステムを提案する。
論文 参考訳（メタデータ） (2021-07-19T02:55:48Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Constrained-optimization Approach Delivers Superior Classical
Performance for Graph Partitioning via Quantum-ready Method [0.0]
グラフ分割は計算インテリジェンス(NP-hard)グラフ問題の重要な集合である。
我々は2つの異なる量子可読法を用いて問題の解をサンプリングした。
どちらのアプローチも、目的的に構築された古典的なグラフパーティショナよりも優れたパーティショナを提供することがよくあります。
論文 参考訳（メタデータ） (2020-06-26T15:55:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。