5 March 2022
Professor Rubin recently posted an article about finding all solutions to a network model: Finding almost all paths. The article mentions two techniques that we explored in our article Taking a dip in the MIP solution pool. Specifically, Professor Rubin says:
To find all solutions, one possible approach is to solve whatever MIP model you choose, then add a "no-good" constraint that eliminates the solution just found (and only that one) and solve again, until eventually the aggregation of "no-good" constraints makes the model infeasible. What I did instead was to use the "populate" command in CPLEX, which accumulates a pool of solutions.
An issue with the CPLEX solution pool is that it isn't guaranteed to find all optimal solutions. So, the Professor also describes a brute force method to find all solutions. The article presents analysis that demonstrates that the brute force performs better in this case – that is, the brute force method is both faster and more reliably finds all solutions.
Although clever solvers are often the best method we have, it is good to remember that brute force can be a useful – and sometimes efficient – method for solving a problem. We used a brute force method for the situation described in our article Job sequencing to minimize completion time. In that situation, brute force enumeration was very effective for small data sets, though it quickly became impractical for large data sets.
In summary, we can extend our list of techniques for finding all solutions to include:
- CPLEX solution pool.
- Eliminate known solutions.
- Brute force enumeration.
If you know of any other methods for finding all (or almost all) solutions to an optimization problem, or you want help with your own models, then please contact us.
