論文の概要: Solving Billion-Scale Knapsack Problems

• arxiv url: http://arxiv.org/abs/2002.00352v1
• Date: Sun, 2 Feb 2020 08:51:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-04 20:22:34.763756
• Title: Solving Billion-Scale Knapsack Problems
• Title（参考訳）: 数十億ドル規模のKnapsack問題の解決
• Authors: Xingwen Zhang, Feng Qi, Zhigang Hua, Shuang Yang
• Abstract要約: クナプサック問題(KPs)は業界では一般的な問題であるが、KPsの解法はNPハードであることが知られ、比較的小さなスケールでのみ抽出可能である。 本稿では,KPをわずかに一般化した形で検討し,分散アルゴリズムを用いて大規模にほぼ最適に解けることを示す。
• 参考スコア（独自算出の注目度）: 11.848773608478703
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Knapsack problems (KPs) are common in industry, but solving KPs is known to be NP-hard and has been tractable only at a relatively small scale. This paper examines KPs in a slightly generalized form and shows that they can be solved nearly optimally at scale via distributed algorithms. The proposed approach can be implemented fairly easily with off-the-shelf distributed computing frameworks (e.g. MPI, Hadoop, Spark). As an example, our implementation leads to one of the most efficient KP solvers known to date -- capable to solve KPs at an unprecedented scale (e.g., KPs with 1 billion decision variables and 1 billion constraints can be solved within 1 hour). The system has been deployed to production and called on a daily basis, yielding significant business impacts at Ant Financial.
• Abstract（参考訳）: クナプサック問題(KPs)は業界では一般的な問題であるが、KPsの解法はNPハードであることが知られ、比較的小さなスケールでのみ抽出可能である。 本稿では,KPを少し一般化した形で検討し,分散アルゴリズムを用いて大規模にほぼ最適に解けることを示す。 提案されたアプローチは、既製の分散コンピューティングフレームワーク(MPI、Hadoop、Sparkなど)でかなり簡単に実装できる。 例えば、我々の実装は、かつてない規模でKPを解くことができる(例えば、10億個の決定変数と10億個の制約を持つKPは、1時間以内に解決できる)、現在知られている最も効率的なKP解法の一つである。 システムはプロダクションにデプロイされ、日々コールされ、ant financialで大きなビジネスへの影響をもたらしている。

関連論文リスト

• Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
  本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。 QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。 そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
  論文  参考訳（メタデータ） (2024-06-14T10:15:03Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• SHAP@k:Efficient and Probably Approximately Correct (PAC) Identification of Top-k Features [16.99004256148679]
  本稿では,トップk識別問題(TkIP)を紹介し,最も高いSHAP値を持つk特徴を特定することを目的とする。 我々の研究の目的は、TkIP解決の文脈において、既存の手法のサンプル効率を改善することである。
  論文  参考訳（メタデータ） (2023-07-10T18:42:45Z)
• Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications [38.98556852157875]
  ランダムな重みの確率分布が未知であるがサンプルデータのみが利用可能であるCCMCKPの実践シナリオに注目した。 CCMCKPを解決するために,データ駆動型適応局所探索(DDALS)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-26T13:35:05Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Deep Reinforcement Learning for Orienteering Problems Based on Decomposition [13.332999086010718]
  本稿では, Knapsack problem (KP) と travel salesman problem (TSP) の2つに分割して, オリエンテーリング問題 (OP) の解法を提案する。 KPソルバはノードの選択に責任を持ち、TSPソルバは適切なパスを設計し、制約違反を判断するKPソルバを支援する。 実験結果から,提案アルゴリズムはトレーニング,推論,能力一般化の点で従来の手法より優れていることが示された。
  論文  参考訳（メタデータ） (2022-04-25T11:45:31Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Stein Variational Model Predictive Control [130.60527864489168]
  不確実性の下での意思決定は、現実の自律システムにとって極めて重要である。 モデル予測制御 (MPC) 法は, 複雑な分布を扱う場合, 適用範囲が限られている。 この枠組みが、挑戦的で非最適な制御問題における計画の成功に繋がることを示す。
  論文  参考訳（メタデータ） (2020-11-15T22:36:59Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。