chassisframework/bin_packer

(WIP) Optimizing bin packing constraint solver for Elixir

BinPacker

WORK IN PROGRESS

A bin-packing constraint solver/optimizer for Elixir.

See the examples.

Included out of the box:

• Constraints

  • OnePerBinConstraint - only one ball with a certain attribute value is allowed in the bin (e.g. one dessert per lunchbox)
  • OnePerGroupConstraint - only one ball with a certain attribute value is allowed per bin group (e.g. one admiral per fleet of ships)

• Optimization Objectives

  • BallsProportionalToBinObjective - sum of ball attribute aims to be proportional to bin attribute (e.g. total process load proportional to cpu)
  • EqualNumBallAttributePerBinObjective - each bin should aim to contain equal numbers of balls with the same attribute (e.g. each truck contains the same number of fragile boxes)
  • EqualNumBallAttributePerGroupObjective - each group of bins should aim to contain equal numbers of balls with the same attribute (e.g. each fleet of ships should contain an equal number of science officers)
  • EqualNumBallBallsPerBinObjective - each bin should contain an equal number of balls (e.g. each album contains the same numer of songs)

Implementation

Based on the variable-neighborhood hill-climbing solver from "Efficient local search for several combinatorial optimization problems" by Mirsad Buljubašić and "Variable Neighborhood Search for Google Machine Reassignment problem" by Gavranović, Buljubašić and Demirović, which was designed to solve the 2012 ROADEF/EURO Machine Reassignment Challenge.

This library generalizes Buljubašić et al's solution by allowing completely custom and pluggable constraints and optimization targets. Additionally, candidate solutions are generated directly by the constraint modules themselves, in order to gradually winnow down the search space as constraints are tested (as opposed to generating random solutions and then testing for constraint violation).

Installation

The package can be installed by adding bin_packer to your list of dependencies in mix.exs:

def deps do
  [
    {:bin_packer, "~> 0.1.0"}
  ]
end

The docs can be found at https://hexdocs.pm/bin_packer.