CODEWITHSUNDEEP
pythonlinear-programmingpulp
Emico
Emico

Reputation: 3

Alternative solution on an assigment problem using PuLP

I'm creating a program to solve assignment problems and so far so good, it works properly and in the end, it solves the problem. I'm using the PuLP library. But I just realized that when the problem has alternative solutions (instead of the unique optimal basic feasible solution) it only shows me the optimal one. Is there any function inside PuLP or any other library that can give me the number of total solutions (for example) or the objective function value for those said alt solutions?

    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

Total = 15.0

Upvotes: 0

Views: 600

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

The basic assignment problem looks like:

 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}

If you solve this, you get one optimal solution x*[i,j]. Let's record this solution in a[i,j,k] with initially k=0. To find a next best solution we can add the constraint:

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

where n is the size of set i (and j) or the number of ones in the solution. This constraint will precisely cut off previous solutions. The algorithm becomes:

  1. solve original assignment problem
  2. set k := 0
  3. store solution in a[i,j,k]
  4. solve problem with additional constraint
  5. if infeasible: STOP
  6. if no more solutions needed: STOP
  7. k := k + 1
  8. go to step 3.

An alternative would be to use a solver that has a so-called solution pool. That will do all of this in just one solve.

For an example see: https://yetanothermathprogrammingconsultant.blogspot.com/2018/04/k-best-solutions-for-assignment-problem.html

Upvotes: 1

Related Questions