Total number of feasible solutions in Python/Gurobi
Answered
Help required.
Hi there !
I was solving a kind of sequential problem that produces a string of alphabets and numbers and with a dummy objective function "m.setObjective(0, GRB.MAXIMIZE)", I'm expecting that Gurobi would generate feasible sequences just based on constraints.
Now I'm sure there would be multiple possible feasible solutions and could someone please help me about how to find how many of those solutions actually exist? I know it sounds more like a permutation/counting problem but cannot do it that way as my original problem is much more complex.
It would be helpful if you can write a line of code along with some explanation.
Thank you so much
Prasanna
-
Hi Prasanna,
Did you check this article How do I find additional solutions to a model?0 -
Yes Marika, I did. I know how to find N different solutions but my question is how would we know whats the maximum value of N ?
0 -
Hi Prasanna,
Counting the total number of feasible solutions is a very difficult problem and this number can easily get gigantic. Gurobi cannot do this since it is not an optimization problem.
You may want to look into the open-source software polymake, which is the best tool for polyhedral geometry. polymake can answer such questions (if the polytope is not too big): the documentation section about lattice points should contain the methods/properties needed for this.
1 -
You could set the PoolSearchMode parameter s.t. the MIP search will continue after a feasible solution was found and set the PoolSolutions parameter to a very high value. In the end, you could check with the model attribute SolCount how many solutions were found. Gurobi will stop if all solutions were found or the parameter PoolSolutions is reached. However, if your problem is very complex Gurobi might take a while to find all solutions.
1 -
Understood. That's all I need.
Thank you so much. Marika Karbstein and Silke Horn
0
Please sign in to leave a comment.
Comments
5 comments