Skip to content

pieterjansevanrensburg/binning-value-problem

Repository files navigation

BinningValueProblem

Overview

For this problem, we are given a set of numbers, and a set of bins with target values.

We wish to allocate the given set of numbers, to the bins, to minimize the difference between the sum of the numbers in each bin and said bin's target value across all bins. Furthermore, each value can only to one bin or no bin at all.

This is done through representing the above problem as a linear programming problem and using discrete-optimization to minimize the differences according to some objective function.

Table of Contents

Mathematical Definition

Suppose we are given a 1 x n vector of floating-point numbers:

F = [f1, f2, f3, ..., fn]

Furthermore, we are also given a set of bins:

B = {1, 2, 3, ..., m}

where j represents the j'th bin and m is the total number of bins.

Also, suppose that we are given a 1 x m vector of target values for the set of bins:

T = [t1, t2, t3, ..., tm]

where tj represents the target value of the j'th bin.

Finally, we are also given an objective function O.

Based on the above, the problem which we wish to solve is to place the values of F into each of the bins in B so as to minimize the value of the objective function O across the differences between the sum of the values within each bin and the target value assigned to each bin. Furthermore, each value in F can only be allocated once or not be allocated at all.

To solve this, we define the binary matrix X, where the elements of X can be described as follows:

xi,j = 1 ⇔ fi is placed in bin j or

xi,j = 0 ⇔ fi is not placed in bin j and

Σjxi,j = 1

∀ i ∈ {1, 2, 3, ..., n}, ∀ j ∈ B

With the above formulation, our problem can be expressed as the following binary linear programming problem:

minimize: O(FX - T)

with respect to the following constraints:

Σjxi,j = 1 ∀ i ∈ {1, 2, 3, ..., n}, ∀ j ∈ B

Solution

This program, given a list of floating-point numbers and a list of target values, automatically generates the above formulation of the problem and then makes use of the PuLP python module to find the optimal solution.

Dependencies

  • PuLP
  • numpy
  • A LP solver for the PuLP frontend to call (options include: COINMP, CPLEX, GLPK, GUROBI, ...)

Contributors

Releases

No releases published

Packages

No packages published

Languages