giorgio93p/bin-packing

Implementation of a branch and bound algorithm for bin packing, where bins can have a lower bound on their capacity

v1.0.2 2023-04-13 07:25 UTC

Requires

• php: >=7.2

Requires (Dev)

• friendsofphp/php-cs-fixer: *
• phpstan/phpstan: >=1.9.0
• phpunit/phpunit: *

AGPL-3.0-or-later

• Georgios V. Pitsiladis

• bin packing

README

The algorithm tries to find the best possible solution (i.e. with the smaller number of bins) by (almost) exhaustively searching the possible solutions. This implies that it is quite slow and will not terminate for an input of more than a few dozen items.

You need to have your items implement the interface BinItem. This includes just a size(): int method. This is meant to be the size of the item. Notice that it must be a strictly positive integer. The size() method of BinItems should run in constant time.

You can pass an iterable (e.g. array or laravel Collection) of BinItems into BinPacking::pack, along with the options of the packing (min and max size of bin). Again, sizes are strictly positive integers. Min size can also be 0.

BinPacking::pack will return an array of bins. Each bin has a method items(), which returns the items of the input that are in the said bin.

For example,

class MyClass implements \Gpits\BinPacking\BinItem
{
    public function size(): int
    {
        //fill this
    }
}

$items = MyClass::getAllItems();

$bins = \Gpits\BinPacking\BinPacking::pack($items, 150, 4000); // for min bin size 150 and max bin size 4000
foreach($bins as $bin){
    foreach($bin->items() as $item){
        //do something with
        $item;
        // where $item instanceof MyClass
    }
}

If you have an item that is too big to fit in any bin, a BinPackingException will be thrown.