論文の概要: A Data-Driven Column Generation Algorithm For Bin Packing Problem in Manufacturing Industry

• arxiv url: http://arxiv.org/abs/2202.12466v1
• Date: Fri, 25 Feb 2022 02:38:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-28 15:00:34.708534
• Title: A Data-Driven Column Generation Algorithm For Bin Packing Problem in Manufacturing Industry
• Title（参考訳）: 製造産業におけるビン充填問題に対するデータ駆動列生成アルゴリズム
• Authors: Jiahui Duan, Xialiang Tong, Fei Ni, Zhenan He, Lei Chen, Mingxuan Yuan
• Abstract要約: ボンパッキング問題は実際のロジスティックなシナリオにおいて広く存在し、パッキング効率を改善し、輸送コストを削減することを目的としている。 厳密な制約は合理的な負荷では扱えないので、既存のアプローチでは最適解を得るのは難しい。 本稿では,Huaweiのパッケージパイプラインから収集した歴史的データから,パッケージングの知識を抽出する。
• 参考スコア（独自算出の注目度）: 12.59265852961433
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The bin packing problem exists widely in real logistic scenarios (e.g., packing pipeline, express delivery), with its goal to improve the packing efficiency and reduce the transportation cost. In this NP-hard combinatorial optimization problem, the position and quantity of each item in the box are strictly restricted by complex constraints and special customer requirements. Existing approaches are hard to obtain the optimal solution since rigorous constraints cannot be handled within a reasonable computation load. In this paper, for handling this difficulty, the packing knowledge is extracted from historical data collected from the packing pipeline of Huawei. First, by fully exploiting the relationship between historical packing records and input orders(orders to be packed) , the problem is reformulated as a set cover problem. Then, two novel strategies, the constraint handling and process acceleration strategies are applied to the classic column generation approach to solve this set cover problem. The cost of solving pricing problem for generating new columns is high due to the complex constraints and customer requirements. The proposed constraints handling strategy exploits the historical packing records with the most negative value of the reduced cost. Those constraints have been implicitly satisfied in these historical packing records so that there is no need to conduct further evaluation on constraints, thus the computational load is saved. To further eliminate the iteration process of column generation algorithm and accelerate the optimization process, a Learning to Price approach called Modified Pointer Network is proposed, by which we can determine which historical packing records should be selected directly. Through experiments on realworld datasets, we show our proposed method can improve the packing success rate and decrease the computation time simultaneously.
• Abstract（参考訳）: ビンパッキング問題は、実際のロジスティックなシナリオ(例えば、パッキングパイプライン、express delivery)に広く存在し、パッキング効率の向上と輸送コストの削減を目標としている。 このNPハード組合せ最適化問題では、ボックス内の各アイテムの位置と量は、複雑な制約と特別な顧客要求によって厳密に制限される。 厳密な制約は合理的な計算負荷では扱えないため、既存の手法では最適解を得るのは難しい。 本稿では,この問題に対処するため,huaweiのパッキングパイプラインから収集した履歴データからパッキング知識を抽出する。 まず、履歴パッキングレコードと入力順序(まとめる順序)の関係を十分に活用することにより、その問題を集合被覆問題として再構成する。 次に、制約処理とプロセス加速という2つの新しい戦略を古典的な列生成手法に適用し、この集合被覆問題を解く。 複雑な制約と顧客要求のために、新しい列を生成するための価格問題の解決コストが高い。 提案された制約処理戦略は、コスト削減の最も負の値を持つ履歴パッキングレコードを利用する。 これらの制約は、これらの歴史的なパッキングレコードにおいて暗黙的に満たされており、制約についてさらなる評価を行う必要がないため、計算負荷は節約される。 カラム生成アルゴリズムの繰り返し処理をさらに排除し,最適化プロセスを高速化するために,修正ポインタネットワークと呼ばれる学習から価格へのアプローチを提案し,どの履歴パッキングレコードを直接選択すべきかを決定する。 実世界のデータセットを用いた実験により,提案手法はパッキング成功率を向上し,同時に計算時間を短縮できることを示す。

関連論文リスト

• Machine Learning and Constraint Programming for Efficient Healthcare Scheduling [0.8287206589886879]
  看護スケジューリング問題(NSP)に取り組む 暗黙の問題解決アプローチでは、学習パターンに埋め込まれる可能性のある制約や目的を通じて、過去のデータを使って新しいソリューションを学習し、生成する機械学習手法を頼りにしています。 提案手法では, 制約や目的が具体的に見えるものではないことを考慮し, 暗黙的アプローチに関する不確実性を補うために, 制約満足度問題フレームワークを用いてまずNSPをモデル化する明示的アプローチを提案する。 我々の暗黙的アプローチは生成したソリューションの実現可能性や最適性を保証するものではないため、データ駆動型アプローチを提案し、NSPを制約として受動的に学習する。
  論文  参考訳（メタデータ） (2024-09-11T18:09:25Z)
• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  大規模データの爆発はシングルマシンシステムの処理能力を上回っている。 分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。 そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-30T13:22:08Z)
• A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
  顧客に対して順次表示される補完アイテムの動的価格設定の問題に対処する。 各項目の価格を個別に最適化するのは効果がないため、補完項目のコヒーレントな価格ポリシーが不可欠である。 実世界のデータからランダムに生成した合成設定を用いて,我々のアプローチを実証的に評価し,制約違反や後悔の観点からその性能を比較した。
  論文  参考訳（メタデータ） (2024-07-08T09:55:31Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Learning with Posterior Sampling for Revenue Management under Time-varying Demand [36.22276574805786]
  価格設定項目やサービスによる収益を最大化するための収益管理問題について議論する。 この問題の1つの課題は、需要分布が未知であり、航空会社や小売業のような実際の応用において時間とともに変化することである。
  論文  参考訳（メタデータ） (2024-05-08T09:28:26Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sysは、条件付き独立性(CI)制約下でのデータ修復に最適な輸送理論を利用するフレームワークである。 我々はSinkhornの行列スケーリングアルゴリズムにインスパイアされた反復アルゴリズムを開発し、高次元および大規模データを効率的に処理する。
  論文  参考訳（メタデータ） (2024-03-04T18:23:55Z)
• Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework [0.0]
  ラグランジアンデュアルフレームワークを用いて,クナプサック問題の解を近似するニューラルネットワークモデルを開発した。 我々は,ベースラインニューラルネットワークと比較して,最適性をわずかに低減した強い制約満足度を示す。
  論文  参考訳（メタデータ） (2023-12-06T10:50:27Z)
• Optimizing Data Collection for Machine Learning [87.37252958806856]
  現代のディープラーニングシステムは、素晴らしいパフォーマンスを達成するために巨大なデータセットを必要とします。 過度に収集したデータは不要な現在のコストを発生させる一方、過度に収集したデータは将来のコストと遅延を引き起こす可能性がある。 本稿では,データ収集を形式的最適データ収集問題としてモデル化するための新しいパラダイムを提案する。
  論文  参考訳（メタデータ） (2022-10-03T21:19:05Z)
• COptiDICE: Offline Constrained Reinforcement Learning via Stationary Distribution Correction Estimation [73.17078343706909]
  オフラインの制約付き強化学習(RL)問題。エージェントは、所定のコスト制約を満たしながら期待されるリターンを最大化するポリシーを計算し、事前に収集されたデータセットからのみ学習する。 定常分布空間におけるポリシーを最適化するオフライン制約付きRLアルゴリズムを提案する。 我々のアルゴリズムであるCOptiDICEは、コスト上限を制約しながら、利益に対する最適政策の定常分布補正を直接見積もる。
  論文  参考訳（メタデータ） (2022-04-19T15:55:47Z)
• A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback [22.17503016665027]
  各アクションが未知の関節分布からランダムな報酬、コスト、ペナルティを返す問題を考える。 我々は、$tt LyOn$という新しい低複雑さアルゴリズムを提案し、$O(sqrtBlog B)$ regretと$O(log B/B)$ constraint-violationを達成することを証明した。 計算コストの低い$tt LyOn$は、Lyapunovをベースとしたアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。
  論文  参考訳（メタデータ） (2021-06-09T16:12:07Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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