Solving nonlinear bin packing optimization problem in python

Question

Is there a straight forward way (e.g. some module with a commonly used solver) to solve a problem derived from the well known bin packing problem (e.g. see https://en.wikipedia.org/wiki/Bin_packing_problem) in python?

In detail, the bin packing problem where s(i) are the items' weights

minimize K = sum_j y_j                    # use as less bins as possible
s.t. sum_i s(i)x_i,j <= B*y_j for all j   # bin capacity B must not be exceeded
     sum_j x_i,j = 1 for all i            # all items have been fit in exactly one bin
     x_i,j, y_j being integer variables in {0,1}

shall be extended towards the following objective function K_nonlinear

minimize K_nonlinear = sum_j (y_j + Std({s(i)}) for all x_i,j =1)
s.t. # the same constraints as the bin packing problem (above)

Hence, not only the number of bins in use should be minimized, but also the standard deviation of the selected items sharing a bin (which will lead to some necessary compromise in general). Therefore the problem becomes nonlinear in my opinion.

I am grateful for any advice how to attack this problem using python (python api would be sufficient, algorithm itself could also be implemented in any other language).

Up to now, I have tried to extend an existing bin packing solver (based on the Coin-or branch and cut solver) about the additional part in the objective function, which failed. Presumably this is due to the induced non-linearity.

Many thanks in advance

Answer 1

Instead of using the standard deviation, it may be easier to minimize the range: max-min. This can be formulated in a linear fashion:

  Minimize xmax-xmin
  xmax >= x[i]  for all i
  xmin <= x[i]  for all i