The bin packing problem is a classic optimization challenge that has far-reaching implications for enterprise organizations across industries. At its core, the problem focuses on finding the most efficient way to pack a set of objects into a finite number of containers or "bins", with the goal of minimizing wasted space.
This challenge is pervasive in real-world applications, from optimizing shipping and logistics to efficiently allocating resources in data centers and cloud computing environments. With organizations often dealing with large numbers of items and containers, finding optimal packing solutions can lead to significant cost savings and operational efficiencies.
For a leading $10B industrial equipment manufacturer, bin packing is an integral part of their supply chain. It is common for this company to send containers to vendors to fill with purchased parts that are then used in the manufacturing process of heavy equipment and vehicles. With the increasing complexity of supply chains and variable production targets, the packaging engineering team needed to ensure assembly lines have the right number of parts available while efficiently using space.
For example, an assembly line needs sufficient steel bolts on-hand so production never slows, but it is a waste of factory floor space to have a shipping container full of them when only a few dozen are needed per day. The first step in solving this problem is bin packing, or modeling how thousands of parts fit in all the possible containers, so engineers can then automate the process of container selection for improved productivity.
| Challenge ❗Wasted space in packaging containers ❗Excessive truck loading & carbon footprint | Objective ✅ Minimize empty space in packaging container ✅ Maximize truck loading capacity to reduce carbon footprint |
|---|---|
 |  |
While the bin packing problem has been extensively studied in an academic setting, efficiently simulating and solving it across complex real-world datasets and at scale has remained a challenge for many organizations.
In some sense, this problem is simple enough for anyone to understand: put things in a box until full. But as with most big data problems, challenges arise because of the sheer scale of the computations to be performed. For this Databricks customer’s bin packing simulation, we can use a simple mental model for the optimization task. Using pseudocode:
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 orientationWhat if we were to run this looping process sequentially using single-node Python? If we have millions of iterations (e.g. 20,000 items x 20 containers x 6 starting orientations = 2.4M combinations), this could take hundreds of hours to compute (e.g. 2.4M combinations x 1 second each / 3600 seconds per hour = ~660 hours = 27 days). Waiting for nearly a month for these results, which are themselves an input to a later modeling step, is untenable: we must come up with a more efficient way to compute rather than a serial/sequential process.
As a computing platform, Databricks has always provided support for these scientific computing use-cases, but scaling them poses a challenge: most optimization and simulation libraries are written assuming a single-node processing environment, and scaling them with Spark requires experience with tools such as Pandas UDFs.
With Ray’s general availability on Databricks in early 2024, customers have a new tool in their scientific computing toolbox to scale complex optimization problems. While also supporting advanced AI capabilities like reinforcement learning and distributed ML, this blog focuses on Ray Core to enhance custom Python workflows that require nesting, complex orchestration, and communication between tasks.
To effectively use Ray to scale scientific computing, the problem must be logically parallelizable. That is, if you can model a problem as a series of concurrent simulations or trials to run, Ray can help scale it. Bin packing is a great fit for this, as one can test different items in different containers in different orientations all at the same time. With Ray, this bin packing problem can be modeled as a set of nested remote functions, allowing thousands of concurrent trials to run simultaneously, with the degree of parallelism limited by the number of cores in a cluster.
The diagram below demonstrates the basic setup of this modeling problem.
The Python script consists of nested tasks, where outer tasks call the inner tasks multiple times per iteration. Using remote tasks (instead of normal Python functions), we have the ability to massively distribute these tasks across the cluster with Ray Core managing the execution graph and returning results efficiently. See the Databricks Solution Accelerator scientific-computing-ray-on-spark for full implementation details.
With the techniques described in this blog and demonstrated in the associated Github repo, this customer was able to:
The combination of automation, batch processing, and optimized container selection has led to measurable improvements for this industrial manufacturer, including a significant reduction in shipping and packaging costs, and a dramatic increase in process efficiency. With the bin packing problem handled, data team members are moving on to other domains of scientific computing for their business, including optimization and linear-programming focused challenges. The capabilities provided by the Databricks Lakehouse platform offer an opportunity to not only model new business problems for the first time, but also dramatically improve legacy scientific computing techniques that have been in use for years.
In tandem with Spark, the de facto standard for data parallel tasks, Ray can help make any “logic-parallel” problem more efficient. Modeling processes that are purely dependent on the amount of compute available are a powerful tool for businesses to create data-driven businesses.
See the Databricks Solution Accelerator scientific-computing-ray-on-spark.
