Re: [Help-glpk] Solution Ranking

[Lou Hafer]

Terry,

> ... how can I get a list of the top 10 or 20 optimal solutions ...

        This question gets asked a lot. Here are a few comments from the peanut
gallery.

        Modern solvers are written to aggressively improve the objective cutoff
as they work. In order to persuade the solver to return more than one
optimal solution, you must disable this mechanism. Whether that's easy /
hard / impossible depends on the solver implementation. (Sorry, my
knowledge of the guts of glpk is not up to answering this question.
Michael's suggestion of lying to glpk with a hook in the feasibility
test is one approach.) It can be difficult to find all the places that
need to be tweaked.

        Now, what do you do with those solutions? Let's assume that the solver
has a callback that runs when a solution is discovered, so that the
client application can harvest the solution and manage the resulting
collection of solutions. Otherwise the solver must maintain the
collection of solutions and report them at the end. This is somewhat
expensive and likely requires its own callback so that the client can
supervise purging the collection (next paragraph).

        If you don't already know the optimal objective, the problem becomes
one of collecting solutions and regularly purging the collection as
better solutions are discovered. Back in the solver, the run time mounts
because you cannot do effective pruning by bound in the search tree. You
can discover hundreds of solutions, only to discard them all when the
search reaches an area of the tree with better objective value.

        And then there's the question of the number of optimal solutions.
Perhaps just a few. Perhaps 1000's. Depends on the relationship of the
polytope and objective function. Now you need to be more specific about
what you want. If there are 100 solutions with the optimal objective,
what are your secondary criteria?

                                                Lou