0

有没有一种直接的方法（例如一些带有常用求解器的模块）来解决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}

应扩展到以下目标函数 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)

因此，不仅要最小化使用的 bin 数量，而且还要最小化共享一个 bin 的选定项目的标准偏差（这通常会导致一些必要的折衷）。因此，在我看来，这个问题变得非线性。

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

到目前为止，我已经尝试扩展现有的装箱求解器（基于 Coin-or 分支和切割求解器）关于目标函数中的附加部分，但失败了。这大概是由于诱导的非线性。

提前谢谢了

4

1 回答 1

1

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

  Minimize xmax-xmin
  xmax >= x[i]  for all i
  xmin <= x[i]  for all i
于 2020-09-18T16:21:53.813 回答