[Help-glpk] Re: finding multiple integer solutions

[Erik Rantapaa]

--- Andrew Makhorin <address@hidden> wrote:
> >I would like to modify the MIP solver to allow for finding multiple optimal
> >solutions, and I would appreciate any comments on a particular approach I am
> >contemplating.
> 
> There is a two-phase procedure. ...

Thank you for your helpful comments.

Is it possible to implement the two-phase procedure as follows?

if the procedure cleanup_the_tree() determines that it would delete all the
nodes in the tree, it instead sets Zopt to best[0] and sets the flag which
is_better() looks at to perform the alternate comparison. Otherwise it
executes as usual.

Here's how I plan to use the multiple solution feature: I'm using the MIP
solver to create a work schedule. However, the people who are running the
program like to have choices. In addition, there are a lot of preferences
which can't be encoded in a linear program. Moreover, I'm not always going
to be around to translate their personal preferences into constraints.
The best solution seems to be to have the MIP solver generate some
possibilities 
(like a dozen or so), and let the them decide on which one they want to use.

With respect to my application, I am happy to report that GLPK (v4.1) is
working very well. I was a little concerned when I read in the manual that
the MIP solver might not be very good for large-scale MIP problems and that
it might not be able to solve problems with more than 100 - 200 integer
variables. My problem has about 1400 binary variables, and the solution time
on a sluggish Pentium 900 is less than 10 minutes.

Erik Rantapaa


__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/