[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]