論文の概要: An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems

• arxiv url: http://arxiv.org/abs/2004.02603v2
• Date: Mon, 20 Apr 2020 15:49:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-17 12:37:16.484112
• Title: An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems
• Title（参考訳）: 2次元および3段階ギロチン充填問題に対するanytime tree searchアルゴリズム
• Authors: Florian Fontan, Luc Libralesso
• Abstract要約: アルゴリズムは64人中1位でした 私たちはそれを一般化し、それが本来設計された特定の問題に有効であるだけでなく、非常に競争力があることを示す。 このアルゴリズムはPackingrと呼ばれる新しいソフトウェアパッケージで実装されている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: [libralesso_anytime_2020] proposed an anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem (https://www.roadef.org/challenge/2018/en/index.php). The resulting program was ranked first among 64 participants. In this article, we generalize it and show that it is not only effective for the specific problem it was originally designed for, but is also very competitive and even returns state-of-the-art solutions on a large variety of Cutting and Packing problems from the literature. We adapted the algorithm for two-dimensional Bin Packing, Multiple Knapsack, and Strip Packing Problems, with two- or three-staged exact or non-exact guillotine cuts, the orientation of the first cut being imposed or not, and with or without item rotation. The combination of efficiency, ability to provide good solutions fast, simplicity and versatility makes it particularly suited for industrial applications, which require quickly developing algorithms implementing several business-specific constraints. The algorithm is implemented in a new software package called PackingSolver.
• Abstract（参考訳）: 関連スポンサーコンテンツ [libralesso_anytime_2020] 2018 roadef/euro challenge glass cutting problem (https://www.roadef.org/challenge/2018/en/index.php)のanytime tree searchアルゴリズムを提案しました。 このプログラムは64人中1位にランクインした。 本稿では,本論文を一般化し,本来設計した特定の問題に対して有効であるだけでなく,非常に競争力があり,多種多様な切断・包装問題に対する最先端のソリューションを文献から返却する。 2段階または3段階の正確なギロチンカット、最初のカットの向きが課されるか否か、アイテムの回転の有無に関わらず、2次元のビンパッキング、複数のナップサック、ストリップパッキング問題に適用した。 効率性、優れたソリューションを提供する能力、シンプルさ、汎用性の組み合わせは、いくつかのビジネス固有の制約を実装するアルゴリズムを迅速に開発する必要がある産業アプリケーションに適している。 このアルゴリズムはPackingSolverと呼ばれる新しいソフトウェアパッケージで実装されている。

関連論文リスト

• A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints [3.9594431485015096]
  2次元負荷制約 (2L-CVRP) を持つ車両ルーティング問題は, 実用的, アルゴリズム的に重要な課題である。 本稿では,高度な機械学習技術,特に注意と再発機構の新たな組み合わせを統合した,正確なアルゴリズムを提案する。 提案アルゴリズムは、標準テストベッドにおけるオープンインスタンスの解決に成功し、機械学習モデルの導入による大幅な改善を実証する。
  論文  参考訳（メタデータ） (2024-06-18T09:58:29Z)
• Learning based 2D Irregular Shape Packing [29.044043493942013]
  2次元不規則な形状パッキングは、3次元モデルのUVパッチをテクスチャアトラス内に配置するために必要なステップであり、コンピュータグラフィックスにおけるメモリ効率の高い外観レンダリングを実現する。 本稿では,学習支援型2次元不規則形状パッキング手法を提案する。 数百のパッチで大きな問題インスタンスを効率的に処理するために、私たちは、ほぼ矩形のパッチサブセットを予測するために、ディープニューラルネットワークポリシーをトレーニングします。
  論文  参考訳（メタデータ） (2023-09-19T05:21:52Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• The Fifteen Puzzle- A New Approach through Hybridizing Three Heuristics Methods [15.91012934719906]
  15のパズル問題は、数世紀にわたって数学の愛好家を魅了してきた最も古典的な問題の1つである。 本稿では,マンハッタン距離(MD),リニアコンフリクト(LC),ウォーキング距離(WD)の3つからなる双方向A*(BA*)探索アルゴリズムを用いた。 BA*サーチの実装は,空間の複雑さを著しく低減し,最適解と準最適解のどちらでも保証できる。
  論文  参考訳（メタデータ） (2023-01-06T07:17:23Z)
• Comparing Heuristics, Constraint Optimization, and Reinforcement Learning for an Industrial 2D Packing Problem [58.720142291102135]
  カットとパッケージングの問題は、ビジネスの収益に直接影響を与えるさまざまな業界で起きている。 機械学習は、このような問題を解決するためにますます使われています。
  論文  参考訳（メタデータ） (2021-10-27T15:47:47Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。 我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。 最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-04T10:33:59Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem [0.0]
  我々は、2018年のROADEF/EUROチャレンジガラス切断問題のために、フランスの企業であるサン=ゴバンが提案した木探索アルゴリズムを提示する。 主な構成要素は、ガイド関数、対称性破壊戦略、擬似支配ルールを備えたメモリバウンドA* (MBA*) と呼ばれる新しい検索アルゴリズムである。 さらに,擬似支配ルールに基づく第2木探索アルゴリズムを設計し,高い優先順位制約を持つ課題事例のいくつかに焦点をあてた。
  論文  参考訳（メタデータ） (2020-04-02T12:51:26Z)

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

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