「箱の中」を考える：RayとDatabricksで解くビンパッキング問題
序章
ビンパッキング問題は、業界を問わず企業組織に広範な影響を及ぼす古典的な最適化の課題です。この問題の核心は、有限の数のコンテナや「ビン」に一連のオブジェクトを最も効率的に詰め込む方法を見つけることで、目標は無駄なスペースを最小限に抑えることです。
この課題は、実世界のアプリケーションで広く見られます。例えば、出荷や物流の最適化、データセンターやクラウドコンピューティング環境でのリソースの効率的な割り当てなどです。組織はしばしば大量のアイテムやコンテナを扱うため、最適なパッキングソリューションを見つけることで、大幅なコスト削減と運用効率の向上を実現できます。
10Bドル規模の先進的な産業機器メーカーにとって、ビンパッキングは供給チェーンの重要な一部です。この会社では、購入した部品を詰めてもらうために、コンテナをベンダーに送ることが一般的です。これらの部品は、重機や車両の製造プロセスで使用されます。供給チェーンの複雑さが増し、生産目標が変動する中で、パッケージングエンジニアリングチームは、組み立てラインに適切な数の部品が利用可能であり、かつ効率的にスペースを使用していることを確認する必要がありました。
例えば、組み立てラインでは、生産が遅れないように十分な鋼のボルトを手元に持っている必要がありますが、1日に数十個しか必要としないのに、それらを満載したコンテナを工場の床面に置いておくのは無駄です。この問題を解決する最初のステップはビンパッキング、つまり何千もの部品が可能なすべてのコンテナにどのように収まるかをモデル化することで、エンジニアはその後、生産性向上のためのコンテナ選択のプロセスを自動化することができます。
| 課題 ❗パッケージングコンテナの無駄なスペース ❗トラックの過剰な積載とカーボンフットプリント |
目標 ✅ パッケージングコンテナの空きスペースを最小限にする ✅ トラックの積載能力を最大化して二酸化炭素排出量を減らす |
|---|---|
 |
 |
技術的な課題
ビンパッキング問題は学術的な設定で広く研究されてきましたが、複雑な実世界のデータセットを横断して効率的にシミュレートし、それを解決することは、多くの組織にとって課題となってきました。
ある意味では、この問題は誰でも理解できるほどシンプルです：箱に物を詰めていき、満杯になるまで詰め続けます。しかし、ほとんどのビッグデータ問題と同様に、計算の規模が非常に大きいために課題が生じます。このDatabricksの顧客のビンパッキングシミュレーションでは、最適化タスクのためのシンプルなメンタルモデルを使用することができます。擬似コードを使用して：
もし、このループ処理を単一ノードのPythonを使って順次実行するとどうなるでしょうか？何百万もの反復がある場合（例えば、20,000アイテム x 20コンテナ x 6の開始方向 = 2.4Mの組み合わせ)、これを計算するのに数百時間かかる可能性があります（例えば、2.4Mの組み合わせ x 1秒 / 1時間あたり3600秒 = 約660時間 = 27日)。これらの結果をほぼ1ヶ月待つことは、それ自体が後のモデリングステップの入力となるため、許容できません：我々は、シリアル/順次的なプロセスよりも効率的な計算方法を見つけなければなりません。
Rayを用いた科学的計算
コンピューティングプラットフォームとして、Databricksは常にこれらの科学計算ユースケースをサポートしてきましたが、それらをスケーリングすることは課題です：最適化やシミュレーションライブラリのほとんどは単一ノードの処理環境を前提に書かれており、それらをSparkでスケーリングするにはPandas UDFsなどのツールに対する経験が必要です。
2024年初頭にDatabricksで一般に利用可能になったRayを使用すると、顧客は複雑な最適化問題をスケールするための新しいツールを手に入れます。強化学習や分散MLのような高度なAI機能をサポートしながら、このブログはRay Coreに焦点を当て、ネスト、複雑なオーケストレーション、タスク間の通信を必要とするカスタムPythonワークフローを強化します。
ビンパッキング問題のモデリング
Rayを効果的に使って科学計算をスケールアップするためには、問題を論理的に並列化する必要があります。つまり、問題を一連の並行シミュレーションや試行としてモデル化できるなら、Rayはそれをスケールアップするのに役立ちます。ビンパッキングは、同時に異なるアイテムを異なるコンテナに異なる向きでテストできるため、これに最適です。Rayを使用すると、このビンパッキング問題はネストされたリモート関数のセットとしてモデル化でき、クラスターのコア数によって制限される並列度で、同時に数千の試行を実行できます。
下の図は、このモデリング問題の基本的なセットアップを示しています。
Pythonのスクリプトはネストされたタスクで構成されており、外部タスクはイテレーションごとに内部タスクを複数回呼び出します。通常のPython関数の代わりにリモートタスクを使用することで、これらのタスクを大規模にクラスタ全体に分散させることが可能になり、Ray Coreが実行グラフを管理し、結果を効率的に返すことができます。実装の詳細については、Databricks Solution Acceleratorのscientific-computing-ray-on-sparkをご覧ください。
パフォーマンス＆結果
このブログで説明されている技術と、関連するGithubのリポジトリで示されている技術を使用すると、この顧客は次のことができました：
- コンテナ選択時間の短縮： 3Dビンパッキングアルゴリズムの採用は、大きな進歩を示しており、より正確で、かつ大幅に速い解決策を提供します。これにより、コンテナ選択に必要な時間が従来のプロセスに比べて40倍短縮されます。
- プロセスを線形にスケールアップ： Rayを使用すると、モデリングプロセスを完了するための時間を、クラスタ内のコア数に線形にスケールアップすることができます。例えば、最初に2.4百万の組み合わせ（単一スレッドで完了するのに660時間かかる）を取り上げます：プロセスを12時間で夜間に実行したい場合、必要なのは：2.4M / (12時間 x 3600秒) = 56コア；3時間で完了させるには、220コアが必要です。Databricksでは、これはクラスタ設定を通じて簡単に制御できます。
- コードの複雑さを大幅に削減： Rayはコードの複雑さを簡素化し、Pythonのマルチプロセッシングとスレッディングライブラリで構築された元の最適化タスクに対するより直感的な代替手段を提供します。以前の実装では、ネストされたロジック構造のため、これらのライブラリについての詳細な知識が必要でした。対照的に、Rayのアプローチはコードベースを単純化し、データチームのメンバーにとってよりアクセスしやすくします。結果として得られるコードは、理解しやすくなるだけでなく、慣用的なPythonの慣行により密接に一致し、全体的な保守性と効率性を向上させます。
科学計算のための拡張性
自動化、バッチ処理、最 適化されたコンテナ選択の組み合わせは、この工業製造業者にとって計測可能な改善をもたらしました。これには、出荷および包装コストの大幅な削減と、プロセス効率の劇的な向上が含まれます。ビンパッキング問題が解決されたことで、データチームのメンバーは、ビジネスにおける科学計算の他の領域、最適化や線形プログラミングに焦点を当てた課題に移行しています。Databricks Lakehouseプラットフォームが提供する機能は、新たなビジネス問題を初めてモデル化するだけでなく、長年使用されてきた伝統的な科学計算技術を劇的に改善する機会を提供します。
データ並列タスクのデファクトスタンダードであるSparkと並行して、Rayはあらゆる「ロジック並列」問題をより効率的にするのに役立ちます。利用可能な計算量に純粋に依存するモデリングプロセスは、データ駆動型ビジネスを創出するための強力なツールです。
Databricks Solution Acceleratorのscientific-computing-ray-on-sparkをご覧ください。
