解决 python 中的非线性装箱优化问题

Question

是否有一种直接的方法（例如，一些具有常用求解器的模块）来解决源自 python 中众所周知的装箱问题（例如，参见 https://en.wikipedia.org/wiki/Bin_packing_problem）的问题？

详细来说，装箱问题，其中 s(i) 是物品的重量

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}

应向以下objective功能扩展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)

因此，不仅应尽量减少使用中的箱子数量，而且应尽量减少所选项目共享一个箱子的标准偏差（这通常会导致一些必要的妥协）。因此，在我看来，这个问题变得非线性了。

对于如何使用 python 解决此问题的任何建议，我非常感谢（python api 就足够了，算法本身也可以用任何其他语言实现）。

到目前为止，我已经尝试扩展现有的装箱求解器（基于Coin-or branch and cut solver）关于objective函数中的附加部分，但失败了。大概这是由于引起的非线性。

非常感谢

Answer 1

与其使用标准差，不如最小化范围更容易：max-min。这可以用线性方式表示：

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

解决 python 中的非线性装箱优化问题

Solving nonlinear bin packing optimization problem in python

optimization

constraints

bin-packing

non-linear

discrete