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