Chess and solution pool with linear programming (2018) (opens in new tab)

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.