Re: [Help-glpk] Multiple solutions for a binary MIP problem?

[Michael Hennebry]

On Fri, 29 Jan 2010, Pavel Klinov wrote:

> I wonder if glpk can provide me with several optimal solutions for a
> 0-1 IP instance (seems not, but I thought I'd ask). I assume I could
> use glpk as an oracle that only returns one solution and simply search
> around (as suggested in, e.g., [1]), but a more direct way would be
> super useful.

I'm not sure about GLPK, but in Symphony,
one could do something like this:
In the feasibility test callback,
reject all solutions when first proposed.
Whenever it gets a new improved solution,
call the add-heuristic function to admit to a second-best solution,
clear the old and lousy solutions and
save the current solution for later.
Whenever it gets a new just as good solution,
just save it for later.

When done, list the saved solution.
There might be a lot of them.

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