Finding best solutions in an IP; Python

[Ferdinand G]

Hello everybody,

I have a problem with my Integer-Program. I've got 3 integer decision variables and I'm trying to retrieve the 10 best solutions, using the code below. Gurobi finds 10 solutions, however, all of them are exactly the same. The values of the decision variables are the same, so is the ObjectiveValue. The documentation says, MIP problems can retrieve the n best solutions. Is there a way to do the same with my Integer-Problem?!

 

from gurobipy import *

 

model = Model("OptMySQL2")

   

  model.setParam(GRB.Param.PoolSearchMode, 2)

  model.setParam(GRB.Param.PoolSolutions, 5)

 

# constraints, variables... 

 

model.optimize()   

  nSolutions = model.SolCount                   

  if model.Status == GRB.OPTIMAL:

       

      for xyz in range(nSolutions):

          model.setParam(GRB.Param.SolutionNumber, xyz)

          for i in fp:

              for j in jt:

                  for l in wol:

                      if x[i,j,l].x > 0.9:

                          print('m %d von t %s .' % (i, j))

      

          for j in jt:

              if y[j].x > 1:

                  print('T %s : %f M.' % (j, y[j].x))

              elif y[j].x == 1:

                  print('T %s : %f M.' % (j, y[j].x))

          print ('Objective: %f' % model.ObjVal)

thanks for your help in advance. 

[Michael Winkler]

Could you provide us with a small problem instance, best in MPS format compressed with 7zip, bzip2, gzip.

Best,

Michael

[Ferdinand G]

Here we go, I hope that's what you need. If not, let me know. Thanks ;-)

[Michael Winkler]

Now I've seen the issue in your Python code. You should use PoolObjVal instead of ObjVal but more importantly you need to use Xn attribute instead of the x attribute to get the value of a variable in solution i. Then you can see that the solutions are indeed different. See also the poolsearch.py example in our example directory.

Best,

Michael

[Ferdinand G]

Hi Michael,

thanks for your help. I didn't know about the xn attribute. I adjusted my code but somehow I still get the same solutions. Is it possible to find multiple solutions even though this is just an IP and not a MIP? I attached the updated code

P.S I know I could have used .xn for the best solution as well.

Am Dienstag, 17. Juli 2018 09:52:55 UTC+2 schrieb Ferdinand G:

[Michael Winkler]

There shouldn't be any duplicates, otherwise it should be a bug. On the first model you send I tested it and I got 5 different solution (but with the same objective value). Could you share your python code? (I use model.getVars() and iterated over all while printing the Xn attribute.)

Best,

Michael

[Michael Winkler]

In your code example above there is nothing anymore of:

model.setParam(GRB.Param.PoolSearchMode, 2)

model.setParam(GRB.Param.PoolSolutions, 5)

 

nSolutions = model.SolCount

     

for xyz in range(nSolutions):

  model.setParam(GRB.Param.SolutionNumber, xyz)

Best, Michael

[Ferdinand G]

Ohh, my bad, sorry. Wrong Version. That's the right one:

from gurobipy import *

import win32com.client
import math
import mysql.connector
import mysql
from collections import defaultdict

def solve(JT, fp, mdk, f , v , n , tp , tc , tcyca , oee , pm , r , t , tm, a, fr, u, cbmin, wol, b, d,c, lok):
  
  model.setParam(GRB.Param.PoolSearchMode, 2)
  model.setParam(GRB.Param.PoolSolutions, 5)

  w = {}
  for j in JT:
      for k in mdk:
          for l in wol
              for h in lok:
                  w[j,k,h,l] = model.addVar(vtype = GRB.BINARY)

  x = {}
  for i in fp:
      for j in JT:
          for l in wol:
              for h in lok:
                  x[i,j,l,h] = model.addVar(vtype = GRB.BINARY)
         
  y = {}
  for j in JT:
      y[j] = model.addVar(vtype = GRB.INTEGER, lb=0, ub=99999)
     
  alpha = {}
  for j in JT:
      for l in wol:
          alpha[j,l] = model.addVar(vtype = GRB.INTEGER, lb=0, ub=99999)
         
  beta = {}
  for j in JT:
      for l in wol:
          for h in lok:
              beta[j,l,h] = model.addVar(vtype = GRB.INTEGER, lb=0, ub=99999)
     
  z = {}
  for j in JT:
      z[j] = model.addVar(vtype = GRB.INTEGER, lb=0, ub=99999)
 
  nmin={}
 
  result = defaultdict(list)
  for (i,j),m in n.items():
      result[i].append(m)
  for i in fp:
      nmin[i] = min(result[i])         
         

  obj = pm*((quicksum((z[j] * f[j]  + (y[j]-z[j])*fr[j]) for j in JT) + \
        quicksum(quicksum(v[j] * x[i,j,l,h] for i in fp for j in JT for l in wol for h in lok) *a/((1+r)**s) for s in t))/cbmin)  + \
        ((1-pm)/len(fp))*(quicksum((n[i,j]*x[i,j,l,h]/nmin[i])for i in fp for j in JT for l in wol for h in lok))
       
  model.setObjective(obj, GRB.MINIMIZE)

  model.update()
 
  for j in JT:
      for l in wol:
          for h in lok:
              model.addConstr(beta[j,l,h]  * tcyca[j,l,h] * oee[j] >= quicksum((x[i,j,l,h]*tp[j]) for i in fp) +\
                              ((quicksum(x[i,j,l,h] for i in fp)-1)*tm[j]) + quicksum(w[j,k,l,h] * tc[j] for k in mdk))
     
  for j in JT:
          model.addConstr(y[j]>= quicksum(alpha[j,l] for l in wol))
 
  for i in fp:
      for j in JT:
          for k in mdk:
              for l in wol:
                  for h in lok:
                      model.addConstr(x[i,j,l,h]*u[i,k]<= w[j,k,l,h])
     
  for i in fp:
      for l in wol:
          for h in lok:
              model.addConstr(quicksum(x[i,j,l,h] for j in JT) == b[i,l]*c[i,h])
     
  for j in JT:
      model.addConstr(z[j] >= ((y[j]-1)/6)+0.001)
     
  for i in fp:
      for j in JT:
          for l in wol:
              model.addConstr(x[i,j,l,h] <= d[i,j])
    
  for j in JT:
      for l in wol:
          for h in lok:
              model.addConstr(alpha[j,l]>=beta[j,l,h])

  model.optimize()   

  nSolutions = model.SolCount                   

  if model.Status == GRB.OPTIMAL:
      print('Objective: %f' % (model.PoolObjVal))
      
      print nSolutions  
     
      for xyz in range(0, nSolutions):

          model.setParam(GRB.Param.SolutionNumber, xyz)
          for i in fp:

              for j in JT:
                  for l in wol:
                      for h in lok:
                          #print('x[%d,%f] = %g' % (i, j, x[i,j].xn))
                          if x[i,j,l,h].xn > 0.9:
                              print('FP %d von T %s gefertigt.' % (i, j))
    
          for j in JT:
              if y[j].xn > 1:
                  print('T %s : %f M.' % (j, y[j].xn))
              elif y[j].xn == 1:
                  print('T %s : %f M.' % (j, y[j].xn))

          print ('Objective: %f' % model.PoolObjVal)
 
         
         
         

Am Dienstag, 17. Juli 2018 09:52:55 UTC+2 schrieb Ferdinand G:

[Michael Winkler]

You should avoid using exact integers when comparing the solution values, e.g., y[j].xn > 0.9 shold be better. Also, you do not print any values for the remaining variables z, alpha, beta, and w. Here the solutions might differ.

Best,

Michael