論文の概要: Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms,
and Applications
- arxiv url: http://arxiv.org/abs/2306.14690v2
- Date: Fri, 15 Dec 2023 03:23:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-18 19:21:49.830517
- Title: Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms,
and Applications
- Title(参考訳): 確率制約付きマルチチョース・ナップサック問題:モデル、アルゴリズム、および応用
- Authors: Xuanfeng Li, Shengcai Liu, Jin Wang, Xiao Chen, Yew-Soon Ong, Ke Tang
- Abstract要約: ランダムな重みの確率分布が未知であるがサンプルデータのみが利用可能であるCCMCKPの実践シナリオに注目した。
CCMCKPを解決するために,データ駆動型適応局所探索(DDALS)アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 38.98556852157875
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The multiple-choice knapsack problem (MCKP) is a classic NP-hard
combinatorial optimization problem. Motivated by several significant real-world
applications, this work investigates a novel variant of MCKP called
chance-constrained multiple-choice knapsack problem (CCMCKP), where the item
weights are random variables. In particular, we focus on the practical scenario
of CCMCKP, where the probability distributions of random weights are unknown
but only sample data is available. We first present the problem formulation of
CCMCKP and then establish two benchmark sets. The first set contains synthetic
instances and the second set is devised to simulate a real-world application
scenario of a certain telecommunication company. To solve CCMCKP, we propose a
data-driven adaptive local search (DDALS) algorithm. The main novelty of DDALS
lies in its data-driven solution evaluation approach that can effectively
handle unknown probability distributions of item weights. Moreover, in cases
with unknown distributions, high intensity of chance constraints, limited
amount of sample data and large-scale problems, it still exhibits good
performance. Experimental results demonstrate the superiority of DDALS over
other baselines on the two benchmarks. Additionally, ablation studies confirm
the effectiveness of each component of the algorithm. Finally, DDALS can serve
as the baseline for future research, and the benchmark sets are open-sourced to
further promote research on this challenging problem.
- Abstract(参考訳): multi-choice knapsack problem (mckp) は古典的なnp-hard combinatorial optimization問題である。
いくつかの重要な実世界の応用によって動機づけられた本研究では、アイテムの重みがランダム変数である確率制約多重クナップサック問題 (CCMCKP) と呼ばれる新しいMCKPの変種を調査する。
特に、ランダムな重みの確率分布が未知であるがサンプルデータのみが利用可能なCCMCKPの実践シナリオに焦点を当てる。
まず、CCMCKPの問題を定式化し、2つのベンチマークセットを確立する。
第1のセットは合成インスタンスを含み、第2のセットは特定の通信会社の実世界のアプリケーションシナリオをシミュレートするために考案される。
CCMCKPを解決するために,データ駆動型適応局所探索(DDALS)アルゴリズムを提案する。
DDALSの主な新規性は、アイテム重みの未知の確率分布を効果的に処理できるデータ駆動型ソリューション評価アプローチにある。
さらに, 未知分布の場合, 確率制約の強度, サンプルデータ量の制限, 大規模問題では, 高い性能を示す。
実験の結果、DDALSは2つのベンチマークで他のベースラインよりも優れていることが示された。
さらに、アブレーション研究はアルゴリズムの各成分の有効性を確認する。
最後に、DDALSは将来の研究のベースラインとして機能し、ベンチマークセットは、この課題の研究をさらに促進するためにオープンソース化されている。
関連論文リスト
- Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。
本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。
最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。
これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
論文 参考訳(メタデータ) (2023-10-18T17:59:45Z) - Doubly Stochastic Matrix Models for Estimation of Distribution
Algorithms [2.28438857884398]
本稿では,自然置換問題のマッチングと割当てにDSM(Douubly Matrices)を用いる方法について検討する。
具体的には、分散アルゴリズムの推定の枠組みを採用し、DSMを置換問題に対する既存の提案と比較する。
二次代入問題の事例に関する予備実験は、この研究の行を検証し、DSMが非常に競争力のある結果が得られることを示した。
論文 参考訳(メタデータ) (2023-04-05T14:36:48Z) - Differentially Private Federated Clustering over Non-IID Data [59.611244450530315]
クラスタリングクラスタ(FedC)問題は、巨大なクライアント上に分散されたラベルなしデータサンプルを、サーバのオーケストレーションの下で有限のクライアントに正確に分割することを目的としている。
本稿では,DP-Fedと呼ばれる差分プライバシー収束手法を用いた新しいFedCアルゴリズムを提案する。
提案するDP-Fedの様々な属性は、プライバシー保護の理論的解析、特に非識別的かつ独立に分散された(非i.d.)データの場合において得られる。
論文 参考訳(メタデータ) (2023-01-03T05:38:43Z) - Sample-based and Feature-based Federated Learning via Mini-batch SSCA [18.11773963976481]
本稿ではサンプルベースおよび特徴ベース連合最適化について検討する。
提案アルゴリズムは,モデルアグリゲーション機構を通じてデータプライバシを保持できることを示した。
また,提案アルゴリズムは,各フェデレーション最適化問題のKarush-Kuhn-Tucker点に収束することを示した。
論文 参考訳(メタデータ) (2021-04-13T08:23:46Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳(メタデータ) (2020-06-11T19:40:38Z) - DDKSP: A Data-Driven Stochastic Programming Framework for Car-Sharing
Relocation Problem [17.440172040605354]
カーシェアリング再配置問題 (CSRP) を不確実な要求下で検討する。
この問題を解決するために、データ駆動カーネルプログラミング(DDKSP)と呼ばれる革新的なフレームワークが提案されている。
提案手法は純パラメトリックアプローチを3.72%,4.58%,11%で上回っている。
論文 参考訳(メタデータ) (2020-01-20T19:04:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。