Chess and solution pool with linear programming (2018)
yetanothermathprogrammingconsultant.blogspot.comMore specifically, using mixed integer linear programming.
I've never seen an MILP used this way, to characterize the entire feasible set (or "solution pool"). Is this one of the fastest ways to do so? The usual branch-and-bound type methods won't apply, since the solver has to enumerate every feasible solution.
The CPLEX docs (https://www.ibm.com/docs/en/icos/22.1.1?topic=solutions-how-...) mention the potential slowness and also the numerical issues the author faces in the article.
Everything happens in the branch and bound tree. Instead of discarding feasible solutions that have worse value than your best one you keep them in a pool.
The author is losing solutions because cplex does smart branching. He can change the branching option to strong branching and he will get the missing solutions. Or he can implement a custom branching callback to ensure that all nodes are visited, even non promising ones.
The solver only has to enumerate every optimal solution.
If you found any optimal solution, you already have the optimal upper and lower bound and therefore you're just iterating through the tree and comparing against the problem relaxation at that point. The worst case scenario for finding multiple solutions is that every solution is optimal but the worst case for a single solution is that you cannot save any work and must check every solution. In other words: the worst case never changes. The algorithm does not get worse in terms of complexity.