使用 PuLP 解决分配问题的替代方案

Question

我正在创建一个程序来解决分配问题，到目前为止一切顺利，它运行正常，最终解决了问题。我正在使用 PuLP 库。但我刚刚意识到，当问题有替代解决方案（而不是唯一的最佳基本可行解决方案）时，它只会向我展示最佳解决方案。 PuLP 或任何其他库中是否有任何函数可以为我提供总解决方案的数量（例如）或这些替代解决方案的 objective 函数值？

    prob.solve()
    print(" ");
    print("* Status: ", LpStatus[prob.status]);
    print(" -------");
    print(" ");

    for v in prob.variables():
        if v.varValue > 0:
            print("------>", v.name,"=", v.varValue);
    
    print("Total = ", value(prob.objective))

状态：最佳

    ------> Asignación:  Agente 1 Tarea 2 = 1.0
    ------> Asignación:  Agente 2 Tarea 4 = 1.0
    ------> Asignación:  Agente 3 Tarea 3 = 1.0
    ------> Asignación:  Agente 4 Tarea 1 = 1.0

总计 = 15.0

Answer 1

基本的分配问题如下所示：

 min sum((i,j), c[i,j]*x[i,j])
 subject to
     sum(j, x[i,j]) = 1  ∀i
     sum(i, x[i,j]) = 1  ∀j
     x[i,j] ∈ {0,1}

如果你解决这个问题，你会得到一个最优解x*[i,j]。让我们在 a[i,j,k] 中记录这个解决方案，最初是 k=0。为了找到下一个最佳解决方案，我们可以添加约束：

     sum((i,j), a[i,j,k]*x[i,j]) ≤ n-1  ∀k

其中 n 是集合 i（和 j）的大小或解中的个数。这个约束将精确地切断以前的解决方案。算法变为：

解决原来的赋值问题
设置k := 0
将解决方案存储在 a[i,j,k]
使用附加约束解决问题
如果不可行：停止
如果不需要更多解决方案：停止
k := k + 1
转到步骤 3。

另一种方法是使用具有 so-called 解决方案池 的求解器。这将在一次解决中完成所有这些。

示例见：https://yetanothermathprogrammingconsultant.blogspot.com/2018/04/k-best-solutions-for-assignment-problem.html

使用 PuLP 解决分配问题的替代方案

Alternative solution on an assigment problem using PuLP

python

linear-programming

pulp