[Top][All Lists]

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

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

From: Michael Hennebry
Subject: Re: [Help-glpk] Multiple solutions for a binary MIP problem?
Date: Fri, 29 Jan 2010 12:35:36 -0600 (CST)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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

reply via email to

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