Re: [Help-glpk] Solution Ranking

[Terry]

More specifically I want what this would give me:

Repeat X times:
1. Run the solver to get an optimum solution.
2. Add a constraint to make the last found optimal solution infeasible.
3. Go to step 1.

These are "the top X solutions" that I want. X could be between 10 and 200. 
These solutions may all be equally optimum. Or, there may be one or more 
equally optimal solutions followed by suboptimal solutions. It could fail to 
find a feasible solution at any point without finding all X solutions. There 
may be many more than X optimal solutions, in which case this would be some 
random set from all the optimal solutions.

The problem I need to solve is an IP or MIP problem. 

Let's ignore the impact of cutting planes for a minute, since I don't 
understand them. Consider just a B&B algorithm. It should be possible to write 
an algorithm that does the following:

1. Run the solver until it finds a feasible solution. Up to this point, nothing 
needs to change from how glpk works now. 
2. Continue searching until it finds an optimal solution, BUT don't prune any 
leaf nodes. Keep all the leaf nodes for when we go looking for more solutions.
3. Add the optimal solution to a top X list.
4. Stop if you have X solutions.
5. Go to step 2 to find the next most optimal solution.

I imagine memory usage could be a serious issue from all the extra leaf nodes 
to store. I can only hope that my problem is small enough that it will be okay.

The next question is, can I make glpk do this? 

I don't need glpk to store the list of optimum solutions it finds, as long as I 
can get them in a callback.

I don't think it will work to just hook into a feasibility callback and tell it 
all solutions are infeasible. Because, my code won't know if a solution is 
optimal. Because, it doesn't know the bound estimates for the other leaf nodes. 
Can glpk give me the best bound estimation over all the other leaf nodes in the 
feasibility callback so I know I'm looking at an optimal solution?

Am I way off base?

Thanks.
Terry


On May 26, 2011, at 12:58 PM, Lou Hafer wrote:

> 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
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk