本書は著者が手動で翻訳したものであり内容の正確性を保証するものではありません。正確な内容に関しては原文を参照ください。
イントロダクション
ビンパッキング問題は、様々な業界におけるエンタープライズ組織において広範囲に影響を与え続けている古典的な最適化問題です。その問題のコアでは、無駄なスペースを最小化するゴールのもと、有限の数のコンテナあるいは「ビン」にオブジェクトのセットをパッキングする最も効率的な方法を見つけ出すことにフォーカスします。
このチャレンジは、出荷や物流の最適化からデータセンターやクラウドコンピューティング環境における効率的なリソース配置など、現実世界のアプリケーションに広く存在しています。企業では多くの場合、膨大な数のアイテムやコンテナを取り扱っていることによって、最適なパッキングの解決策を特定することで、大きなコスト削減やオペレーション上の効率性につながります。
$10Bの業界装置製造のリーディングカンパニーにおいては、サプライチェーンにおいてビンパッキングが重要なものとなっています。このような企業においては、重工の装置や自動車の製造プロセスで使用される発注部品が搭載されたコンテナをベンダーに送るということはよくあります。サプライチェーンの複雑性や製造ターゲットの変動性の増加によって、パッケージングエンジニアリングチームは、スペースを効率的に使いつつも、組み立てラインに適切な数の部品があるようにする必要がありました。
例えば、ある組み立てラインには十分な数のボルトがあるので製造が遅延することはありませんが、一日に数十個のみを必要とするにも関わらず、ボルトを満載したコンテナを置いておくことは工場フロアのスペースの無駄となります。この問題を解決する最初のステップがビンパッキングであり、利用できる全てのコンテナに数千の部品がどのように収まるのかをモデリングすることで、エンジニアは生産性を改善するために、コンテナを選択するプロセスを自動化することができます。
| 課題 ❗パッケージングコンテナの無駄なスペース ❗過剰なトラックの積載やカーボンフットプリント |
目的 ✅パッケージングコンテナの空きスペースの最小化 ✅カーボンフットプリントを削減するためにトラックの積載容量の最大化 |
|---|---|
 |
 |
技術的課題
ビンパッキング問題は学術領域で徹底的に研究されていますが、多くの企業において、複雑な現実の大規模データセットの効率的なシミュレーションや解決はいまだに課題となっています。
いくつかのケースでは、この問題は誰にとっても理解できるほど十分にシンプルなものとなります: 満杯になるまで物を入れるということです。しかし、多くのビッグデータ問題と同じように、実行する計算のスケールが増加することで課題が発生します。このDatabricksのお客様のビンパッキングのシミュレーションにおいては、最適化のためにシンプルなメンタルモデルを用いることができます。以下の疑似コードを使います:
For (i in items): The process needs to run for every item in inventory (~1,000’s)
↳ For (c in containers): Try the fit for every type of container (~10’s)
↳ For (o in orientations): The starting orientations of the first item must each be modeled (==6)
↳ Pack_container Finally, try filling a container with items with a starting orientation
シングルノードのPythonを用いてシーケンシャルにこのループ処理を実行したとしたらどうなるでしょうか？数百万のイテレーション(例 20,000アイテム x 20コンテナ x 6つの開始時の方向 = 2.4Mの組み合わせ)の場合、これは計算処理に数百時間 (例 2.4Mの組み合わせ x 処理ごとに1秒 / 1時間は3600秒 = ~660時間 = 27日)を要することになります。後ほどのモデリングステップの入力となるこれらの結果を得るために約1ヶ月を要し、到底受け入れられる物ではありません: 直列/シーケンシャルなプロセス以外のより効率的な方法を考え出す必要があります。
Rayによる科学技術計算
Databricksはコンピューティングプラットフォームとして、これらの科学技術計算ユースケースに常にサポートを提供してきていましたが、これらのスケーリングは課題を生み出します: ほとんどの最適化やシミュレーションのライブラリは、シングルノードの処理環境を前提として記述されており、Sparkを用いたスケーリングには、Pandas UDFのようなツールの経験を必要としていました。
2024年前半のDatabricksにおけるRayの正式提供によって、お客様は自身の科学技術計算の道具箱に、複雑な最適化問題をスケールさせるための新たなツールを追加できることになりました。強化学習や分散MLのような高度なAI能力もサポートしていますが、この記事では、ネスト化、複雑なオーケストレーション、タスク間のコミュニケーションを必要とするカスタムPythonワークフローを強化得するRay Coreにフォーカスします。
ビンパッキング問題のモデリング
科学技術計算をスケールさせるために効率的にRayを使うには、問題は論理的に並列化可能である必要があります。すなわち、同時実行される一連のシミュレーションやトライアルとして問題をモデル化できるのであれば、Rayがスケーリングの助けとなります。ビンパッキングは、同時に異なる方向にある様々なコンテナに含まれる様々なアイテムをテストできるので、とてもこの条件に当てはまっています。Rayによって、ビンパッキング問題はネストされたリモート関数のセットとしてモデル化され、クラスターのコア数によって限定される並列度で、同時に数千のトライアルを実行できるようになります。
以下の図では、この問題のモデリングの基本的な状況を示しています。
このPythonスクリプトは、イテレーションごとに外側のタスクが内側のタスクを複数回呼び出すネスト化されたタスクから構成されています。(通常のPython関数ではなく)リモートタスクを用いることで、効率的に実行グラフを管理し、結果を返却するRay Coreを搭載したクラスターにこれらのタスクを大規模に分散させる能力を手に入れることになります。実装の詳細に関しては、Databricksソリューションアクセラレータのscientific-computing-ray-on-sparkをご覧ください。
パフォーマンスと結果
この記事で説明されているテクニックを用いて、関連Githubリポジトリをデモすることで、このお客様においては以下を行えるようになりました:
- コンテナ選択時間の削減: 3Dビンパッキングアルゴリズムを導入することで、コンテナ選択に必要となる時間をレガシーなプロセスと比較して40xのファクターで削減し、より正確なだけではなくより高速なソリューションを提供することで、大きな進歩を示しました。
- プロセスを線形にスケール: Rayによって、モデリングプロセスを完了する時間がクラスターのコア数に対してスケールするようになりました。(シングルスレッドでは660時間を要する)上述の2.4M組み合わせの例を考えてみましょう: プロセスを夜間の12時間実行したいのであれば、2.4M / (12時間 x 3600秒) = 56コアを必要とします。3時間で完了したいのであれば220コアが必要となるでしょう。Databricksにおいては、これはクラスター設定を通じて簡単にコントロールすることができます。
- コードの複雑性を劇的に削減: Rayはコードの複雑性をシンプルにし、Pythonのマルチプロセッシングやスレッディングのライブラリで構築されたオリジナルの最適化タスクに対する直感的な代替案を提供します。上述の実装では、ネスト化されたロジック構造のため、これらのライブラリのきめ細かい知識を必要としました。一方、Rayのアプローチはコードベースをシンプルにし、データチームのメンバーがよりアクセスしやすくなります。最終的なコードは理解が簡単になるだけではなく、Pythonの慣用的なプラクティスによりアラインすることになり、全体的なメンテナンス性と効率性を強化することになります。
科学技術計算における拡張可能性
自動化、バッチ処理、最適化されたコンテナ選択は、この製造企業に大きな改善をもたらしました。これには、出荷、パッケージングコストの大幅な削減、プロセスの効率性における劇的な改善が含まれます。ビンパッキング問題に取り組むことでデータチームのメンバーは、最適化や線形プログラミングにフォーカスした課題を含む自分たちのビジネスにおけるその他の化学計算の領域に足を踏み出しています。Databricksレイクハウスプラットフォームが提供する能力によって、初めて取り組むビジネス問題をモデリングするだけでなく、数年使われていたレガシーな科学技術計算テクニックを劇的に改善する機会を提供します。
データ並列タスクのデファクトスタンダードであるSparkと組み合わせることで、Rayは「ロジック並列」問題をより効率的にする助けとなります。利用できる計算資源の量に純粋に依存するモデリングプロセスは、データドリブンのビジネスを生み出すために企業にとってパワフルなツールとなります。
Databricksソリューションアクセラレータのscientific-computing-ray-on-sparkをご覧ください。