带约束离散矩阵极小化问题的求解

Question

我试图用python解决一个订单最小化问题。因此，我将M个订单分配给N个工人。每个工人都有一个基本的能量水平X_i，它被收集在向量X中。同样，每个订单都有一个特定的能量消耗E_j，它被收集在E中。这样说来，我试图解决以下问题

其中Y是某个最佳能级，范数为2范数。在约束条件下，任何列加起来正好是一个，因为订单应该由一个工人完成，并且只能由一个工人完成。我查看了scipy.optimize，但据我所知，它似乎不支持这种优化

你知道Python中有什么工具可以解决这种离散优化问题吗

Answer 1

答案取决于标准。如果你想要2-范数，这是一个MIQP（混合整数二次规划）问题。它是凸面的，因此周围有很多解算器（例如Cplex、Gurobi、Xpress，这些都是商业解算器）。它也可以由MINLP解算器处理，比如BonMin（开源）。Pyomo和CVXPY是一些有帮助的建模工具

如果需要1-范数，可以将其表示为线性MIP（混合整数规划）模型。有相当多的MIP解算器，如Cplex、Gurobi、Xpress（商业）和CBC、GLPK（开源）。一些建模工具有Pyomo、CVXPY和PuLP