論文の概要: Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem
- arxiv url: http://arxiv.org/abs/2310.04471v2
- Date: Mon, 8 Jul 2024 17:09:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-10 03:28:33.881923
- Title: Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem
- Title（参考訳）: カラービン包装問題に対する高速近傍探索ヒューリスティックス
- Authors: Renan F. F. da Silva, Yulle G. F. Borges, Rafael C. S. Schouery,
- Abstract要約: CBPP(Colored Bin Packing Problem)は、Bin Packing Problem(BPP)の一般化である。
CBPPは、一組のアイテムを、それぞれ重量と色で詰めて、限られた容量のビンで梱包する。
CBPPに対するBPPの適応と新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuristics and new heuristics for the CBPP. Moreover, we propose a set of fast neighborhood search algorithms for CBPP. These neighborhoods are applied in a meta-heuristic approach based on the Variable Neighborhood Search (VNS) and a matheuristic approach that combines linear programming with the meta-heuristics VNS and Greedy Randomized Adaptive Search (GRASP). The results indicate that our matheuristic is superior to VNS and that both approaches can find near-optimal solutions for a large number of instances, even for those with many items.
- Abstract（参考訳）: CBPP(Colored Bin Packing Problem)は、Bin Packing Problem(BPP)の一般化である。
CBPPは、一組のアイテムを、それぞれ重量と色で梱包し、限られた容量のビンに詰め込み、使用済みビンの数を最小化し、同じ色の2つのアイテムを同じビンに並べて充填できないという制約を満たす。
本稿では,CBPPに対するBPPヒューリスティックスと新しいヒューリスティックスの適応を提案した。
さらに,CBPPの高速近傍探索アルゴリズムを提案する。
これらの地区は、変数近傍探索(VNS)に基づくメタヒューリスティックなアプローチと、線形プログラミングとメタヒューリスティックなVNSとGreedy Randomized Adaptive Search(GRASP)を組み合わせた数学的アプローチに適用される。
その結果,我々の数学的手法はVNSよりも優れていることが示唆され,多くの項目を持つ場合であっても,両手法は多数の事例に対してほぼ最適解を見出すことができた。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Machine Learning for the Multi-Dimensional Bin Packing Problem:
Literature Review and Empirical Evaluation [52.560375022430236]
Bin Packing Problem (BPP) は、よく確立された最適化(CO)問題である。
本稿では、まずBPPを定式化し、その変種と実用的制約を導入する。
次に,多次元BPPのための機械学習に関する総合的な調査を行う。
論文 参考訳（メタデータ） (2023-12-13T12:39:25Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Hybrid Approach for Solving Real-World Bin Packing Problem Instances
Using Quantum Annealers [0.8434687648198277]
実世界の3次元Bin Packing Problems(Q4RealBPP)を解くためのハイブリッド量子古典的フレームワークを提案する。
Q4RealBPPは、3dBPPの現実指向のインスタンスの解決を許可しており、産業や物流部門でよく評価されている制限について検討している。
論文 参考訳（メタデータ） (2023-03-01T14:04:50Z) - Hybrid Quantum-Classical Heuristic for the Bin Packing Problem [0.8434687648198277]
1次元Bin Packing Problem (1dBPP) を扱うためのハイブリッド古典量子法を提案する。
古典的な計算サブルーチンは、量子サブルーチンによって与えられる部分集合から問題に対する完全な解を構築する。
ハイブリッドな解法として、我々はH-BPPと呼ぶ。
論文 参考訳（メタデータ） (2022-04-12T09:05:27Z) - Combinatorial Pure Exploration with Bottleneck Reward Function and its
Extension to General Reward Functions [13.982295536546728]
ボトルネック報酬関数 (CPE-B) を用いたコンビネーションピュア探索問題について, 一定の信頼性と固定予算設定の下で検討する。
固定信頼と固定バジェットのアルゴリズムを両立させ,固定信頼設定のサンプル複雑性を低く設定する。
さらに、CPE-Bを一般報酬関数(CPE-G)に拡張し、非自明なサンプル複雑性を持つ一般非線形報酬関数に対する最初の固定信頼アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-24T06:47:51Z) - Combinatorial Pure Exploration with Full-bandit Feedback and Beyond:
Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。
本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
論文 参考訳（メタデータ） (2020-12-31T12:40:52Z) - Exploration in two-stage recommender systems [79.50534282841618]
2段階のレコメンデータシステムは、スケーラビリティと保守性のために業界で広く採用されている。
このセットアップの鍵となる課題は、各ステージの最適性能が最適なグローバルパフォーマンスを暗示していないことである。
そこで本研究では,ランクとノミネーター間の探索戦略を同期させる手法を提案する。
論文 参考訳（メタデータ） (2020-09-01T16:52:51Z) - Adaptive Large Neighborhood Search for Circle Bin Packing Problem [8.855116523397935]
我々は、円ビンパッキング問題(CBPP)と呼ばれる新しいパッキング問題に対処する。
CBPPは、使用済みのビンの数を最小限に抑えるために、複数の正方形のビンに円のアイテムを密に詰め込むことである。
本稿では,Corner Occupying Action (GACOA) を用いたグレディアルゴリズムを用いて,初期レイアウトを構築する適応型大近傍探索(ALNS)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-20T10:14:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。