論文の概要: Randomized heuristic repair for large-scale multidimensional knapsack problem

• arxiv url: http://arxiv.org/abs/2405.15569v1
• Date: Fri, 24 May 2024 14:01:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-27 13:50:09.488693
• Title: Randomized heuristic repair for large-scale multidimensional knapsack problem
• Title（参考訳）: 大規模多次元クナップサック問題に対するランダムなヒューリスティック修復法
• Authors: Jean P. Martins,
• Abstract要約: 多次元クナップサック問題(MKP)は、最大総利益項目のサブセットを決定するNPハード最適化問題である。 本稿では, 品質を劣化させることなく, 補修液の変動性を向上する効率補修法を提案する。
• 参考スコア（独自算出の注目度）: 0.5439020425819
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The multidimensional knapsack problem (MKP) is an NP-hard combinatorial optimization problem whose solution is determining a subset of maximum total profit items that do not violate capacity constraints. Due to its hardness, large-scale MKP instances are usually a target for metaheuristics, a context in which effective feasibility maintenance strategies are crucial. In 1998, Chu and Beasley proposed an effective heuristic repair that is still relevant for recent metaheuristics. However, due to its deterministic nature, the diversity of solutions such heuristic provides is insufficient for long runs. As a result, the search for new solutions ceases after a while. This paper proposes an efficiency-based randomization strategy for the heuristic repair that increases the variability of the repaired solutions without deteriorating quality and improves the overall results.
• Abstract（参考訳）: 多次元クナップサック問題(MKP)は、容量制約に違反しない最大利益項目のサブセットを決定するNPハード組合せ最適化問題である。 大規模なMKPインスタンスは、その硬さのため、通常はメタヒューリスティックス(メタヒューリスティックス)の標的となる。 1998年、チューとビーズリーは、最近のメタヒューリスティックにはまだ関係のある効果的なヒューリスティックな修復を提案した。 しかし、その決定論的性質のため、そのようなヒューリスティックなソリューションの多様性は長期にわたって不十分である。 結果として、新しい解の探索はしばらくして終了する。 本稿では,修復液の分散性を向上し,品質を劣化させることなく,全体的な結果を改善する,ヒューリスティック修復のための効率に基づくランダム化戦略を提案する。

関連論文リスト

• A Re-solving Heuristic for Dynamic Assortment Optimization with Knapsack Constraints [14.990988698038686]
  資源knapsack制約下でのMNLを用いたマルチステージ動的アソシエーション最適化問題について検討する。 正確な最適動的アソシエーション解を計算的に抽出可能とすることで、決定論的線形プログラムを周期的に最適化する再解法を実践的戦略として採用する。 目的の分母を制約に効果的に変換するエポックな新しい再解法を提案する。
  論文  参考訳（メタデータ） (2024-07-08T02:40:20Z)
• Evolutionary Multi-Objective Algorithms for the Knapsack Problems with Stochastic Profits [13.026567958569965]
  我々は、ある商品の利益に対する一定の信頼を保証するため、利益を伴うknapsack問題のバージョンを検討する。 利益率制約付きクナップサック問題の多目的定式化を導入し, 両目的性評価法を3つ設計する。 両設定のベンチマークにおいて,提案手法の有効性を示す。
  論文  参考訳（メタデータ） (2023-03-03T03:28:51Z)
• Diversifying Investments and Maximizing Sharpe Ratio: a novel QUBO formulation [0.0]
  本稿では,記述されたタスクに対する新しいQUBOの定式化を提案し,数学的詳細と必要な仮定を提供する。 我々は、利用可能なQUBOソルバを用いて結果を得るとともに、この用語で大規模な問題に対処するハイブリッドアプローチの振る舞いについて議論する。
  論文  参考訳（メタデータ） (2023-02-23T19:15:44Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• Stein Variational Model Predictive Control [130.60527864489168]
  不確実性の下での意思決定は、現実の自律システムにとって極めて重要である。 モデル予測制御 (MPC) 法は, 複雑な分布を扱う場合, 適用範囲が限られている。 この枠組みが、挑戦的で非最適な制御問題における計画の成功に繋がることを示す。
  論文  参考訳（メタデータ） (2020-11-15T22:36:59Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Simplified Swarm Optimization for Bi-Objection Active Reliability Redundancy Allocation Problems [1.5990720051907859]
  信頼性冗長性割り当て問題(RRAP)は、システム設計、開発、管理においてよく知られた問題である。 本研究では, コスト制約を新たな目標として変更することにより, 両対象RRAPを定式化する。 提案課題を解決するために,ペナルティ関数を備えた新しい簡易スワム最適化 (SSO) ,実効1型ソリューション構造,数値ベースの自己適応型新しい更新機構,制約付き非支配型ソリューション選択,および新しいpBest代替ポリシーを開発した。
  論文  参考訳（メタデータ） (2020-06-17T13:15:44Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)
• Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives [12.634782111072585]
  本稿では,各項目の重みが容量制約の対象となる動的チャンス制約knapsack問題について考察する。 目的は、総重量がキャパシティを超える確率に基づく総利益を最大化することである。 与えられた解に対する最小限のキャパシティを見積もる追加の目的を導入する。
  論文  参考訳（メタデータ） (2020-02-17T04:36:15Z)

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

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