help-glpk
[Top][All Lists]

## Re: [Help-glpk] Solution Ranking

 From: Michael Hennebry Subject: Re: [Help-glpk] Solution Ranking Date: Fri, 27 May 2011 10:39:56 -0500 (CDT) User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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

--