論文の概要: Features for the 0-1 knapsack problem based on inclusionwise maximal solutions

• arxiv url: http://arxiv.org/abs/2211.09665v1
• Date: Wed, 16 Nov 2022 12:48:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 17:05:25.460128
• Title: Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
• Title（参考訳）: 包含的最大解に基づく0-1knapsack問題の特徴
• Authors: Jorik Jooken, Pieter Leyman and Patrick De Causmaecker
• Abstract要約: 我々は任意の 0-1 knapsack 問題インスタンスの IMS に関連する新しい計算上の問題をいくつか定式化する。 約540CPU時間でスーパーコンピュータ上の2つの大きなデータセットを計算し、計算コストのかかる14の特徴を導出する。 提案する特徴は,問題事例の実証的硬度に関連する重要な情報を含むことを示す。
• 参考スコア（独自算出の注目度）: 0.7734726150561086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decades of research on the 0-1 knapsack problem led to very efficient algorithms that are able to quickly solve large problem instances to optimality. This prompted researchers to also investigate whether relatively small problem instances exist that are hard for existing solvers and investigate which features characterize their hardness. Previously the authors proposed a new class of hard 0-1 knapsack problem instances and demonstrated that the properties of so-called inclusionwise maximal solutions (IMSs) can be important hardness indicators for this class. In the current paper, we formulate several new computationally challenging problems related to the IMSs of arbitrary 0-1 knapsack problem instances. Based on generalizations of previous work and new structural results about IMSs, we formulate polynomial and pseudopolynomial time algorithms for solving these problems. From this we derive a set of 14 computationally expensive features, which we calculate for two large datasets on a supercomputer in approximately 540 CPU-hours. We show that the proposed features contain important information related to the empirical hardness of a problem instance that was missing in earlier features from the literature by training machine learning models that can accurately predict the empirical hardness of a wide variety of 0-1 knapsack problem instances. Using the instance space analysis methodology, we also show that hard 0-1 knapsack problem instances are clustered together around a relatively dense region of the instance space and several features behave differently in the easy and hard parts of the instance space.
• Abstract（参考訳）: 0-1クナプサック問題の研究は、非常に効率的なアルゴリズムを生み出し、大きな問題のインスタンスを迅速に最適に解けるようになった。 これにより研究者は、既存のソルバにとって難しい比較的小さな問題インスタンスが存在するかどうかを調査し、どの特徴がその困難さを特徴付けるかを調べることができた。 従来、著者らはハード0-1knapsack問題インスタンスの新たなクラスを提案し、いわゆる包摂的最大解(IMS)の性質がこのクラスにとって重要な硬度指標であることを示した。 本稿では,任意の 0-1 クナプサック問題の imss に関する新たな計算問題をいくつか定式化する。 先行研究の一般化とimssに関する新しい構造的結果に基づき、これらの問題を解決するために多項式と擬似多項時間アルゴリズムを定式化する。 このことから,計算コストのかかる14種類の特徴を導出し,約540CPU時間でスーパーコンピュータ上の2つの大きなデータセットを計算した。 提案手法は,様々な0-1クナップサック問題の経験的ハードネスを正確に予測できる機械学習モデルを訓練することにより,文献から得られた初期の特徴に欠けていた問題インスタンスの経験的ハードネスに関する重要な情報を含むことを示す。 また, インスタンス空間解析手法を用いて, ハード0-1クナプサック問題インスタンスが比較的密集した領域の周辺に集結し, いくつかの特徴がインスタンス空間の容易かつ硬い部分で異なる挙動を示す。

関連論文リスト

• MATH-Perturb: Benchmarking LLMs' Math Reasoning Abilities against Hard Perturbations [90.07275414500154]
  各種モデルにおけるMATH-P-Hardの性能低下を観察する。 また、学習した問題解決スキルを盲目的に適用する新しい形態の記憶に関する懸念も提起する。
  論文  参考訳（メタデータ） (2025-02-10T13:31:46Z)
• Easy2Hard-Bench: Standardized Difficulty Labels for Profiling LLM Performance and Generalization [126.27645170941268]
  さまざまなドメインにまたがる6つのベンチマークデータセットのコレクションであるEasy2Hard-Benchを紹介します。 これらのデータセット内の各問題は、数値的な難易度スコアで注釈付けされる。 様々な難易度にまたがる性能と一般化能力を総合的に分析する。
  論文  参考訳（メタデータ） (2024-09-27T03:49:56Z)
• Sparse Representations, Inference and Learning [0.0]
  弱い長距離相互作用を伴う多種多様な問題に使用できる汎用フレームワークを提案する。 キャビティ法の開発により、これらの問題をレプリカ対称レベルでどのように研究できるかを確かめる。
  論文  参考訳（メタデータ） (2023-06-28T10:58:27Z)
• Preliminary Results on Using Abstract AND-OR Graphs for Generalized Solving of Stochastic Shortest Path Problems [25.152899734616298]
  最短経路問題(SSP)は、現実世界におけるゴール指向の問題である。 SSPの計算における重要な課題は、適度な大きさの問題を難解に解決する方法を見つけることである。 提案手法は任意のSSPソルバに組み込んで階層的最適ポリシーを計算可能であることを示す。
  論文  参考訳（メタデータ） (2022-04-08T21:30:47Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights [15.402666674186936]
  本研究では,ランダム化探索アルゴリズム (RSA) と基本進化アルゴリズム (EA) のランタイム解析を行った。 本稿では,重み相関と異なる種類の利益プロファイルが,確率制約条件下での両アルゴリズムの実行動作にどのように影響するかを示す。
  論文  参考訳（メタデータ） (2021-02-10T23:40:01Z)
• Unravelling Small Sample Size Problems in the Deep Learning World [69.82853912238173]
  筆者らはまず,アルゴリズムが動作空間に応じて分離される小さなサンプルサイズ問題に対するディープラーニングアルゴリズムのレビューを行う。 第2に,特徴マップの最も識別性の高い部分からグローバル情報を抽出することに焦点を当てた動的注意プーリング手法を提案する。
  論文  参考訳（メタデータ） (2020-08-08T13:35:49Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• The Backbone Method for Ultra-High Dimensional Sparse Machine Learning [3.7565501074323224]
  超高次元問題にスケールできるスパースかつ解釈可能な機械学習手法を実現する汎用フレームワークであるBackbone法を提案する。 私たちは、分で107ドル、時間で108ドル、分で105ドルという決定ツリーの問題でスパースレグレッションの問題を解決する。
  論文  参考訳（メタデータ） (2020-06-11T16:43:02Z)
• Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems [5.370742369840518]
  機械学習モデルでは、最適解の一部ではないと予測される最適化問題から決定変数を強引に除去できることを示す。 1) 問題の特徴,2) 問題のサイズ,3) 問題タイプ。 未使用変数の予測精度は、テストインスタンスがトレーニングセットからさらに離れているため、自然に劣化するが、異なるTSP問題でテストしても、機械学習モデルは有用な予測を行う。
  論文  参考訳（メタデータ） (2020-05-12T15:09:20Z)

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

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