For ILP problems, does GUROBI gaurantee finding all possible solutions?
AnsweredAs I mentioned in the title, for instance of using PoolSearchMode = 2, I am wondering if
Does GUROBI gaurantee finding all possible solutions for ILP?
This question arose from reading the paper “Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function”
paper link: https://www.mdpi.com/1999-4893/18/3/140
In the section 1.1's last paragraph, the paper mentions that gurobi does not implement unrestricted subtree method or one-tree method that SCIP and CPLEX has implemented as a internal function.
However, https://docs.gurobi.com/projects/optimizer/en/current/features/solutionpool.html
the official document from gurobi mentions that using PoolSearchMode = 2, the solver searches the entire feasible space.
In order for the solver to search the entire feasible space… - gurobi doc
I think that these two documents collides, making me confuse.
I want to get answer to the question, and if possible, I want to know which method or algorithm the solver uses to get all solutions for the problem.
-
-
Gurobi Staff
Hi Junseo,
I went through the first sections of the paper you linked and here are some comments:
-
Does GUROBI gaurantee finding all possible solutions for ILP?
No, this is technically not guaranteed by any solver. The only way to ensure that all solutions where found is to perform a complete enumeration of the search tree. This is of course possible in theory, but in practice it's intractable for most models. -
Method not implemented in Gurobi
This information in the paper is not accurate. Gurobi's PoolSearchMode works in a similar way as to what is described in the paper for CPLEX. The correct information and the different modes for the pool search are described accurately in the PoolSearchMode documentation. - Motivation of the paper
The authors claim that the main motivation for the development of their method is that Gurobi returns multiple solutions that differ in integer variables not appearing in the objective, which are usually auxiliary modeling variables in their application. However, this can be avoided by setting the PoolIgnore attribute for variables with zero objective coefficients. Gurobi only considers solutions as “different” when they differ in at least one variable where the PoolIgnore attribute is set to false. Therefore, this would result in the behavior the authors are describing.
Let me know if you have any further questions on the solution pool features and functionality.
Best regards,
Vassilios
0 -
-
Hi Vassilios
I have a query. I have not read the paper the OP posted.
Is the CPX_PARAM_SOLNPOOLINTESITY setting of 4, documentation here: https://www.ibm.com/docs/en/icos/22.1.0?topic=parameters-solution-pool-intensity same as setting PoolSearchMode setting in Gurobi to 2? Using the former, in CPLEX, I have been able to get what I believe are all feasible integer points of a bounded polyhedron by simultaneously setting CPX_PARAM_POPULATELIM to the maximum possible value.
Thank you.
0 -
-
Hi Vassilios,
Thank you for your great answers, they were extremely helpful.
However, there are still a few subtleties that I am trying to clarify, so I would like to ask one additional question.
Regarding your comment in response to my first question, “This is of course possible in theory, but in practice it's intractable for most models,” I am a bit unsure what exactly “intractable” means in this context.
In my case, the problem size is not very large, and the model was solved within a reasonable computation time.
If I use PoolSearchMode = 2, which the Gurobi documentation states searches the entire feasible region, and the solver terminates normally, can I interpret this as meaning that Gurobi has found the complete set of feasible optimal solutions?
Thank you very much for your time and clarification.
Best regards,
Junseo0 -
-
-
Hi,
Is the CPX_PARAM_SOLNPOOLINTESITY setting of 4, documentation here: https://www.ibm.com/docs/en/icos/22.1.0?topic=parameters-solution-pool-intensity same as setting PoolSearchMode setting in Gurobi to 2? Using the former, in CPLEX, I have been able to get what I believe are all feasible integer points of a bounded polyhedron by simultaneously setting CPX_PARAM_POPULATELIM to the maximum possible value.
From the CPLEX documentation it seems like this approach is more similar to setting PoolSearchMode=1 and PoolSolutions=MAXINT, since you would be looking for a complete enumeration. A complete enumeration of the branch-&-bound tree is the only way to ensure that all feasible solutions were found, both in Gurobi and CPLEX (or any MIP solver really).
I am a bit unsure what exactly “intractable” means in this context.
Intractable means that the size of a complete branch-&-bound tree and the number of possible feasible solutions can easily “explode”, even for moderately-sized models. So even though complete enumeration might be possible in theory, in practice it's often not, due to memory and/or time restrictions.
If I use PoolSearchMode = 2, which the Gurobi documentation states searches the entire feasible region, and the solver terminates normally, can I interpret this as meaning that Gurobi has found the complete set of feasible optimal solutions?
Termination in this case means that the solver has found the n best solutions, where n is controlled by the PoolSolutions parameter. The default value is 10.
A few of the finer details are explained in the Solution Pool Documentation.
Best regards,
Vassilios
0 -
Please sign in to leave a comment.
Comments
4 comments