Repeating identical solutions in the solution pool because of three possible values (1, 0, -1) for binary variables

Answered

November 30, 2021 05:47 Edited

This is a part of my script that reads out the solutions in the solution pool. There are more than 300 variables in the model and they are all in binary form. I set the PoolSolutions to 10,000 and it turns out that most of the solutions are identical because there are actually 3 possible values, which are 1, 0 and -0 for binary variables. As shown in the figure below, the solutions 0 and solution 1 only differ in some variables such as T[0,2], which is -0 in solution 1 and 0 in solution 0.

I am using python 3.9.7 and Gurobi 9.5. I also set PoolSearchMode to 1 as a post in community indicated. But it only makes the value -0 vanish in the 1st solution.

for solcnt in range (m.SolCount):
    for v in m.getVars():
        # VarName: Variable name
        # X=x: Value in the current solution
        print('%s %g' % (v.varName, v.Xn))

Comments

14 comments

Official comment
Simranjit Kaur

Gurobi Staff

December 06, 2024 00:22
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
Jaromił Najman

Gurobi Staff

December 03, 2021 14:03 Edited
Could you share the model file and a minimal working code to make this issue reproducible? Please have a look at Posting to the Community Forum for additional information on sharing files within the Community Forum.

Could you also try reducing the IntFeasTol value to rule out possible numeric issues? Alternatively, you could try turning on the IntegralityFocus parameter.

Best regards,
Jaromił
0
Xuan Zhou

December 04, 2021 01:11 Edited
Hi Jaromil,

Thanks for your advice! However, I tried IntegralityFocus=1 and IntFeasTol=1e-9 and they both do not help a lot in solving the repeating solution problem.

The link below is the .lp file of my script. Please kindly check it.

Thank you very much for your response!

https://drive.google.com/file/d/1BQkaIGp0O1DKTGodWv7cCDz6zZzVsQh-/view?usp=sharing

Best regards,

Xuan
0
Jaromił Najman

Gurobi Staff

December 06, 2021 09:09
Hi Xuan,

Thank you for uploading the file. I was not able to reproduce this issue. Could you share a small code snippet which writes out the files you posted in the screenshot?

Moreover, the objective value I get for the model you uploaded is \(100.1599\) while in your screenshot the objective value is \(55.3795\). Are you sure that the LP file is the correct one?

Best regards,
Jaromił
0

Xuan Zhou

December 06, 2021 20:42 Edited

# this part of script writes out the file shown in the screenshot

for solcnt in range (m.SolCount):
        m.Params.SolutionNumber = solcnt # the # of solution in the pool that we want to refer to
        out_file += "solution:" + str(solcnt) + '\n'
        out_file += 'Obj: ' + str(m.PoolObjVal) + '\n'

        for v in m.getVars():
        # VarName: Variable name
        # X=x: Value in the current solution
                out_file += ('%s %g\n' % (v.varName, v.Xn)) 

# write out the out_file
f = open("gurobi_report", "w")
f.writelines(out_file)
f.close()

Hi Jaromil,

Thanks for your reply!

The objective value in my previous screenshot is 55.3795 because it was produced by my previous objective function. Sorry for the confusion! The figure below is the output file now.

Best regards,

Xuan

Jaromił Najman

Gurobi Staff

December 07, 2021 08:37
Hi Xuan,

Could you please double check whether all solution point values are identical except for the \(0,-0\)? In my tests, the solution points differ in the \(\texttt{C}\) variables, e.g., variable \(\texttt{C[46]=1}\) in one solution but \(\texttt{C[46]=0}\) in another. The \(0\) and \(-0\) difference does not matter because it is just a floating point representation, cf. Signed zero.

If you find a solution point which is identically also in the \(\texttt{C}\) variables, could you please write two of those points out and share the files, cf. Posting to the Community Forum?

Best regards,
Jaromił
0

Jaromił Najman

Gurobi Staff

December 07, 2021 09:35

For completeness, I used this very rudimentary script to check for duplicates:

import gurobipy as gp

m = gp.read("gurobi_script.lp")
# optimize model first to find 10k solutions
m.setParam("PoolSearchMode",1)
m.setParam("PoolSolutions",10000)
m.optimize()
# initialize some data
vars=m.getVars()
nSolutions = m.SolCount
solutions = []
# save all solution points and their objective value
for i in range(nSolutions):
  m.setParam(GRB.Param.SolutionNumber, i)
  m.update()
  sol = []
  for v in vars:
    sol.append((v.VarName,v.Xn,m.PoolObjVal))
  solutions.append(sol)
# compare solution points with the same objective value
for i in range(nSolutions):
  sol1 = solutions[i]
  for k in range(i+1,nSolutions):
    sol2 = solutions[k]
    # if objective value of points is different, proceed with next
    if sol1[0][2] != sol2[0][2]:
      continue
    are_different = False
    # check if two solution points differ in at least one variable
    for j in range(len(sol1)):
      if abs(sol1[j][1]-sol2[j][1]) > 0.5:
        are_different = True
        break;

    # if no difference has been found, write out the two points and terminate
    if not are_different:
      print("found duplicate solutions!")
      f1 = file.open("sol1.sol","w")
      f2 = file.open("sol2.sol","w")
      for j in len(sol1):
        f1.write("%s %f"%(sol1[j][0],sol2[j][0]))
        f2.write("%s %f"%(sol2[j][0],sol2[j][0]))
      f1.close()
      f2.close()
      m.dispose()
      exit()
    else:
      print("there is a difference between solution points %d and %d with objective value %f"%(i,k,sol1[j][2]))

print("finished and no duplicates have been found")
m.dispose()

Best regards,
Jaromił

Xuan Zhou

December 08, 2021 04:14 Edited
Hi Jaromil,

Thank you for your reply and continous attention to my post!

1> For the repeating solutions, I searched the top 10k and most of them are repeating solutions. I just found out that except the solutions that differs only in value 0 and -0, there are also some repeating solutions that are exactly the same. Actually the 0, -0 themselves do not bother me because they can be both regarded as 0. But because of the large amount of repeating solutions caused by -0, 0 and other repeating solutions that are exactly the same, I cannot find the solution that I want in the top 10k solution pools (the solution that I want to find is not the solution with highest objective value, but a solution that has a relatively high objective value and it can probably be found in the top 10k solution pools if there are no repeating solutions).

The related files are shared with google drive and below please find the link:

The top 10k solutions: https://drive.google.com/file/d/1APfLtsNzvNN7DO69UXrvmblD6MH8QMkK/view?usp=sharing

The script that finds out the exactly same repeating solutions: https://drive.google.com/file/d/1JxVsbVr8AMwiSc_P-Jv9_R0zSdiuM42d/view?usp=sharing

The report of the exactly same repeating solutions (because there are too many of them, just 1000 pairs of repeating solutions found will be displayed to this file, or the file will be too large to be opened): https://drive.google.com/file/d/1h-OuV4bj8sRvbHM-ZxwDC4X4x0dulX9w/view?usp=sharing

My parameter settings:

PoolSearchMode = 1

IntegralityFocus = 1

Other parameters that I tried before:

I once tried IntFeasTol=1e-9 but it didn't help with my problem.

Making MIPGap large will greatly reduce the number of repeating solutions in the top 10k solution pools. But unfortunately, it will always skip the solution I want.

2> What is the effect of m.update() ?

Thank you very much!

Best regards,

Xuan
0
Jaromił Najman

Gurobi Staff

December 08, 2021 09:04 Edited
Hi Xuan,

Thank you for the files. I am trying to reproduce the behavior but was still not able to. I noticed that your code seems to find more solution points with value 100.1599 while on my side Gurobi finds only 2. Could you share the log file of the Gurobi run computing the 10k solutions? Could you try running the script I posted above on your side?

2> What is the effect of m.update() ?

The update() method is used to process any pending model modifications. Gurobi uses a lazy update mode to save computation/communication time. The update method is especially important when working with a remote server. It is usually not required when working on a local machine.

Best regards,
Jaromił
0
Xuan Zhou

December 09, 2021 06:11
Hi Jaromil,

I changed your script a little bit. The solutions generated by your script is very similar to that generated by my original python Gurobi script. The range of the objective value of top 10k solutions are both from 100.16 to 99.3635. But the order differs a little bit. Both sets of 10k solutions contain lots of repeating solutions. The related files are shown below:

The script that calls .lp file after changing:

https://drive.google.com/file/d/1e4_Vif8cif5lcRqaUVZ1u6nnRF8qO0rT/view?usp=sharing

The output files including the repeating pairs of solutions:

https://drive.google.com/file/d/1I2L0AJ4V9p6PKWWBsyFEl7xywXYReXpv/view?usp=sharing

The top 10k solutions produced by the script:

https://drive.google.com/file/d/1OECN19UCsHl1-XX7goFifl1O_Va-c9xp/view?usp=sharing

The log file of the script:

https://drive.google.com/file/d/1ItV2KPrDrGyA5S5ssZKYfMXuQqLKIoHb/view?usp=sharing

I also changed the parameter IntegralityFocus from 1 to 0 (this parameter also seems not helpful to the repeating solutions problem) to make it the same as the parameter settings in your script. All the files below are releated to my original Gurobi python file.

The top 10k solutions:

https://drive.google.com/file/d/1APfLtsNzvNN7DO69UXrvmblD6MH8QMkK/view?usp=sharing

The log file:

https://drive.google.com/file/d/1oGPdwAfzyhd6W0Mp86cUFo60xcZC4yVy/view?usp=sharing

The top 1k paris of same solutions:

https://drive.google.com/file/d/1h-OuV4bj8sRvbHM-ZxwDC4X4x0dulX9w/view?usp=sharing

Thank you very much!

Best regards,

Xuan
0
Jaromił Najman

Gurobi Staff

December 09, 2021 09:18
Hi Xuan,

Thank you for the files. In the log file, I noticed that you are using version 9.1.2. There was indeed an issue with duplicate solutions in this version which has been resolved in version 9.5.0. Could you upgrade to the latest Gurobi version and try again to see whether this problem perceives?

Best regards,
Jaromił
0
Xuan Zhou

December 09, 2021 19:24
Hi Jaromil,

I just checked my log file and found out the Gurobi is running at edition 9.1.2. But I have already installed the latest version Gurobi 9.5 as shown in the figure below. I wonder why the Gurobi is still running at old version when new version has been installed?

Thank you!

Best regards,

Xuan
0
Jaromił Najman

Gurobi Staff

December 10, 2021 09:14
Hi Xuan,

How do you execute Gurobi? Do you use your native Python installation or do you use a virtual environment or conda?

Best regards,
Jaromił
0
Xuan Zhou

December 13, 2021 07:57
Hi Jaromil,

I just found out that it was because there were 2 Gurobi packages in my computer and the terminal was calling the 9.1.2 version package. Now I have fixed the problem. Thanks for your help and wish you a happy holiday!

Best regards,

Xuan
0

Post is closed for comments.

Repeating identical solutions in the solution pool because of three possible values (1, 0, -1) for binary variables

Comments

Didn't find what you were looking for?