論文の概要: Deep Reinforcement Learning on Item-Compatibility Graphs for One-Dimensional Bin Packing

• arxiv url: http://arxiv.org/abs/2609.25397v1
• Date: Mon, 21 Sep 2026 20:39:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-23 18:04:04.101024
• Title: Deep Reinforcement Learning on Item-Compatibility Graphs for One-Dimensional Bin Packing
• Title（参考訳）: 1次元ビンパッキングのための項目適合性グラフの深部強化学習
• Abstract要約: 1次元ビンパッキング問題 (1D-BPP) は、物流や製造からクラウドリソース管理に至るまでのアプリケーションに対する古典的なNPハード最適化問題である。 1D-BPPのためのエンドツーエンド,サイズに依存しないグラフ強化学習フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The one-dimensional bin packing problem (1D-BPP) is a classical NP-hard combinatorial optimization problem with applications ranging from logistics and manufacturing to cloud resource management. Although deep reinforcement learning (DRL) has become a competitive paradigm for data-driven optimization, most learned packing methods target 2D and 3D variants, and intelligent learned solvers for 1D-BPP remain scarce. In this paper, we present a novel end-to-end, size-agnostic graph reinforcement learning framework for 1D-BPP. We formulate the packing process as a Markov decision process on an item-compatibility graph, serving as a structural knowledge representation in which every action merges two partial bins that fit together. A graph neural network actor-critic policy extracts relational features from this representation and is trained through reinforcement learning and decoded by stochastic beam search, enabling a single trained model to generalize zero-shot to instances of any size. We conduct a systematic empirical study across graph encoders, DRL algorithms, reward functions, training distributions, and hyperparameters. Evaluated zero-shot on the full BPPLIB benchmark against a constructive heuristic, a grouping genetic algorithm, and recent learned methods, our data-driven policy lowers the mean optimality gap of the constructive heuristic from 2.66\% to 2.31\%, with the largest gains on structured instances. Against learned baselines evaluated on the same benchmark, it attains a lower gap on most of the nine families and is far more stable across instance distributions. On the hardest benchmark family, it outperforms a state-of-the-art learned solver that relies on column generation and integer programming, while using no solver at all. A grouping genetic algorithm remains ahead overall, and we analyze where and why the residual gap arises.
• Abstract（参考訳）: 1次元ビンパッキング問題 (1D-BPP) は、物流や製造からクラウドリソース管理に至るまでのアプリケーションに対する古典的なNPハード組合せ最適化問題である。 深部強化学習(DRL)はデータ駆動最適化の競争パラダイムとなっているが、ほとんどの学習されたパッキング手法は2Dと3Dの変種をターゲットにしており、1D-BPPのインテリジェントな学習解法は依然として乏しい。 本稿では,1D-BPPのためのエンドツーエンド,サイズに依存しないグラフ強化学習フレームワークを提案する。 アイテム適合性グラフ上のマルコフ決定プロセスとしてパッキングプロセスを定式化し、全てのアクションが結合する2つの部分的なビンをマージする構造的知識表現として機能する。 グラフニューラルネットワークアクター批判ポリシーは、この表現から関係性を抽出し、強化学習を通じてトレーニングされ、確率的ビームサーチによってデコードされる。 我々は,グラフエンコーダ,DRLアルゴリズム,報酬関数,トレーニング分布,ハイパーパラメータを網羅した系統的研究を行った。 BPPLIBベンチマークの全ゼロショットを、構築的ヒューリスティック、グループ化遺伝的アルゴリズム、および最近の学習手法に対して評価し、我々のデータ駆動ポリシーは、構築的ヒューリスティックの平均最適性ギャップを2.66\%から2.31\%に下げ、構造化インスタンスの最大のゲインを下げる。 同じベンチマークで評価された学習ベースラインに対して、9つのファミリーのほとんどで低いギャップを達成でき、インスタンス分布全体ではるかに安定している。 最も難しいベンチマークファミリでは、カラム生成と整数プログラミングに依存した最先端の学習解決器よりも優れており、解決器は一切使用していない。 グループ化遺伝的アルゴリズムは概して先進的であり、残差が生じる場所と理由を分析する。

関連論文リスト

• MMR1: Enhancing Multimodal Reasoning with Variance-Aware Sampling and Open Resources [113.33902847941941]
  VAS (Variance-Aware Sampling) は、Variance Promotion Score (VPS) によって導かれるデータ選択戦略である。 我々は、1.6MのCoT冷間開始データと15kのRLQAペアを含む大規模かつ慎重にキュレートされたリソースをリリースする。 数学的推論ベンチマークによる実験では、キュレートされたデータと提案されたVASの有効性が示されている。
  論文  参考訳（メタデータ） (2025-09-25T14:58:29Z)
• FORGE: Foundational Optimization Representations from Graph Embeddings [3.9124823111588163]
  既存の学習ベースの手法では、各問題分布に専用のモデルをトレーニングする必要がある。 本稿では,ベクトル量子化グラフオートエンコーダを事前トレーニングするフレームワークであるGraph Embeddingsの基盤最適化表現について紹介する。 両タスクとも,商用最適化解法の性能向上と,最先端の学習手法の性能向上を図る。
  論文  参考訳（メタデータ） (2025-08-28T00:15:57Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• GraphLearner: Graph Node Clustering with Fully Learnable Augmentation [76.63963385662426]
  Contrastive Deep Graph Clustering (CDGC)は、異なるクラスタにノードをグループ化するために、コントラスト学習のパワーを活用する。 我々は、GraphLearnerと呼ばれる、完全学習可能な拡張を備えたグラフノードクラスタリングを提案する。 学習可能な拡張器を導入し、CDGCのための高品質でタスク固有の拡張サンプルを生成する。
  論文  参考訳（メタデータ） (2022-12-07T10:19:39Z)
• Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
  アクティブラーニングフレームワークは、最も有益なデータポイントのラベル付けを積極的に要求することで、データアノテーションのコストを削減することを目的としている。 提案手法には、不確実性に基づく手法、幾何学的手法、不確実性に基づく手法と幾何学的手法の暗黙の組み合わせなどがある。 本稿では, サンプル選択戦略における効率的な探索・探索トレードオフを実現するために, 不確実性に基づくフレームワークと幾何学的フレームワークの両方の最近の進歩を革新的に統合する。 本フレームワークは,(1)正確な後続推定,(2)計算オーバーヘッドと高い精度のトレードオフの2つの利点を提供する。
  論文  参考訳（メタデータ） (2022-10-11T20:20:20Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• GLAN: A Graph-based Linear Assignment Network [29.788755291070462]
  深層グラフネットワークに基づく学習可能な線形代入問題の解法を提案する。 合成データセットによる実験結果から,本手法は最先端のベースラインよりも優れていることがわかった。 また,提案手法を一般的なマルチオブジェクトトラッキング(MOT)フレームワークに組み込んで,エンド・ツー・エンドでトラッカーをトレーニングする。
  論文  参考訳（メタデータ） (2022-01-05T13:18:02Z)
• Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
  分散制約最適化問題(DCOP)は、最適化問題の重要なサブクラスである。 本稿では,DCOPのための新しい非巡回グラフスキーマ表現を提案し,グラフ表現を組み込むためにグラフ注意ネットワーク(GAT)を利用する。 我々のモデルであるGAT-PCMは、幅広いDCOPアルゴリズムを向上するために、オフラインで最適なラベル付きデータで事前訓練される。
  論文  参考訳（メタデータ） (2021-12-08T09:24:10Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Deep Reinforcement Learning of Graph Matching [63.469961545293756]
  ノードとペアの制約下でのグラフマッチング(GM)は、最適化からコンピュータビジョンまでの領域におけるビルディングブロックである。 GMのための強化学習ソルバを提案する。 rgmはペアワイズグラフ間のノード対応を求める。 本手法は,フロントエンドの特徴抽出と親和性関数学習に焦点をあてるという意味において,従来のディープグラフマッチングモデルと異なる。
  論文  参考訳（メタデータ） (2020-12-16T13:48:48Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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