Re: [Help-glpk] Solution Ranking

[Michael Hennebry]

On Thu, 26 May 2011, Terry wrote:

> 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.

That is almost what I understood.
I had that that they all had to be optimal.
> 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:

There isn't any.

> 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.

It shouldn't be if you do it right.

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

That depends on the precise definition of glpk.

> 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?

The most straightforward method would be to modify GLPK
to put the pruning value solely under programmer control.
Once you have X solutions,
require future solutions to be better than the worst of the X.

Probably you can do it with just callbacks.
I think that there is a callback that will let you
specify the value of a newly discovered solution.
If you still have fewer than X solutions,
the new solution should be valueless.
If, after possible purging, you now have X solutions,
the new solution should have the value of worst.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."