Solving Bin Packing with Powershell

Welcome to another post regarding optimization algorithms in Powershell. Today we're going to examine the Bin Packing problem and a way to solve it using Powershell.

Bin Packing is the problem of separating a set of items into subsets, in a way that their size does not exceed a specific value and the number of sets is the minimum possible. As you can imagine, there are multiple applications of such an algorithm in everyday life, such as in logistics (e.g. containers on ships), storage, and even job scheduling. More information on the Bin Packing problem is also available on Wikipedia.  

To make things easier for people not familiar with programming languages like C# and Python, I've decided to convert my C# code to a cmdlet that will access Powershell objects and will separate them into groups.

The cmdlet is called Get-BinPacking and is available as part of my AdvancedAlgorithms module published on PowershellGallery here, starting from version 1.2.0.0.

There are two ways to pass data to it, the Items parameter and the pipeline. There are also two mandatory parameters, BinSize which is the size of the bins, and WeightPropertyName that is the name of the property of the items that will serve as the weight for the selection. Let's go through some examples.

Assuming a collection of items that have a name and a weight created with the below commands:

$items = New-Object -TypeName System.Collections.ArrayList

$obj1 = New-Object -TypeName PSObject `
                   -Property @{Name = "Item1"; Weight = 10}
$items.Add($obj1) | Out-Null

$obj2 = New-Object -TypeName PSObject `
                   -Property @{Name = "Item2"; Weight = 20}
$items.Add($obj2) | Out-Null

$obj3 = New-Object -TypeName PSObject `
                   -Property @{Name = "Item3"; Weight = 30}
$items.Add($obj3) | Out-Null

the Get-BinPacking command for a bin size of 50 would be:

Get-BinPacking -BinSize 50 `
               -Items $items `
               -WeightPropertyName Weight

The result is an even distribution into two bins:

Using the Powershell pipeline makes it even easier:

$items |
    Get-BinPacking -BinSize 50 `
                   -WeightPropertyName Weight

One of the real-world examples of a bin packing problem I've come across is the distribution of mailboxes in Microsoft Exchange Databases. When migrating from one Exchange organization to another - or event upgrading from a major version, the mailboxes have to be migrated to the new databases. Databases on the other hand have suggested maximum size, if not a size that is allowed by the hardware of the machine. Thus, we have to evenly distribute the mailboxes to the new databases, according to their size.

Let's assume that we have a CSV file that contains the UserPrincipalName and size information for each mailbox, like below:

 The easiest way to get the optimal distribution is to pass this information to the Get-BinPacking cmdlet using the pipeline:

I've selected a bin size of 250 and the Size property to be used as the property that contains the weight of the items.

The output of the command is similar to Group-Object, the objects have been separated into groups called bins and a new object is returned for each bin.

To make things a bit more clear, I'll display the items in each bin:

As you can see, the mailbox of user8 has been moved to the first bin, in order to have the maximum bin utilization with a total size of 250.

I hope this helps!