How to find all solutions to a mixed integer programming problem?
AnsweredHi,
I would like to know if it is possible to get all possible solutions from Gurobi rather than just 1. I think it is easiest to explain on a simple problem. Suppose that there are 4 agents that can create groups. Possible groups are given by matrix G where rows are possible groups and each column corresponds to an agent.
For example, there could be 6 possible groups (at most 2 agents in each group in this example).
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1
Suppose that each group has an associated value. The values for each of the 6 groups that we have could be:
100
50
100
100
50
100
The question is which groups should be implemented in order to maximize the sum of values, but such that no agent is asked to be in more than one group. For example, group 1 and 2 cannot be implemented because then agent 1 would need to be in two groups at once which is impossible.
Then if G is the matrix from above with 6 rows and 4 columns; V is a column vector with group values, then we simply need to find x (a row vector with 6 elements) that solves:
max x*V
x G <= 1
x binary (either 0 or 1 elements where latter means that the group is implemented)
In this example there are two solutions. Either implementing groups 1 and 6 which would give x=(1,0,0,0,0,1) as the solution or implementing groups 3 and 4 which would give x=(0,0,1,1,0,0) as the solution.
Gurobi will only give me one solution. Is it possible to get all of them (I do not know how many there might be in general)? The solutions could be in R or Python.
Thank you in advance!
-
-
Gurobi Staff
Hi Aleksandrs,
You can use Gurobi's Solution Pool feature. Specifically, check out the usage of the parameter PoolSearchMode=2.
You may find our KB article How do I find additional solutions to a model? helpful too.
Best regards,
Simran1 -
-
Hi Simranjit,
Thank you very much for the answer. I am new to gurobi, and even after reading the manual I cannot figure out where I should write PoolSearchMode=2 . Could you please help.
In my Python code I have the following lines:
my_model = gp.Model(...
my_model.addVars(...
my_model.setObjective(...
my_model.addConstrs(...
my_model.setParam('TimeLimit', 60)
my_model.optimize()
and then in order to see the solution on the screen I have:
for v in my_model.getVars():
print(v.varName, v.x)So, my question is where I should write PoolSearchMode=2 ? And also, if there are several solutions, how can I choose to print solution1, solution2, etc. ?
Thank you in advance!
0 -
-
-
PoolSearchMode is a parameter. You can set it as follows:
my_model.Params.PoolSearchMode = 2
See the Python Parameter Examples section of the documentation for more information. Be sure to also set the PoolSolutions parameter to the number of solutions you want to find.
The number of stored solutions is given by the SolCount model attribute. You can retrieve multiple solutions and their objective values by using the SolutionNumber parameter, Xn variable attribute, and PoolObjVal model attribute. For example:
for i in range(my_model.SolCount):
my_model.Params.SolutionNumber = i
sol = my_model.getAttr("Xn")
objval = my_model.PoolObjVal1 -
-
Thank you, it works!
However, after testing this, it looks like it finds 10 best solutions. I am only interested in those solutions that maximize the objective value. That is, suppose I find the optimal solution. Then I am only interested in seeing other solutions if the give me exactly the same value of the objective function. Right now I am using your code to get 10 solutions, and then I check manually when a solution has a lower value of the objective function and I stop there. But is there an easier way such that it gives me all solutions automatically? I have read some articles on the website, and it looks like PoolObjBound could be useful. However, before running the code I do not know what the value should be. What should I write in Python such that pooled solutions only include solutions with the maximal possible value of the objective function? Thank you!
0 -
-
-
You can set the PoolSolutions parameter to the number of solutions you want to find. If you're only interested in optimal solutions, you can set the PoolGap or PoolGapAbs parameter to a very small value.
0 -
Please sign in to leave a comment.
Comments
5 comments