Re: [Help-glpk] Using MIP to get a less-than-optimal solution?

[Brady Hunsaker]

On Thu, 2004-04-15 at 08:25, Philip Warner wrote:
> This may be a silly question, but is it possible to get GLPK to give a 
> faster, less-than-optimal solution to a problem?
> 
> eg. if I have an optimal (non-integer) LP solution, and am happy with any 
> integer solution that is at most 20% more expensive, can I use MIP to find it?
> 

This capability is fairly standard for MIP solvers, but has not been
implemented in GLPK in an easy way yet.  Andrew has been working for the
last several releases on a new Integer Optimization Suite (IOS), which
will make this sort of thing easy and make GLPK much better at handling
MIPs.  IOS also includes the idea of user-defined callback functions
such as what you are requesting.

For the time being it is not easy, however.  I think it is because the
current integer enumeration setup does not carefully keep track of the
overall LP bound as the search is progressing (I could be mistaken about
that).

IOS is not part of glpsol yet, but most of the routines are available if
you are willing to do your own coding to use them.  Look in
include/glpios.h and src/glpios*.c.    Alternatively you could hack the
current integer enumeration code to check against a bound based on the
original LP relaxation value (which is different than the true LP bound
as the b&b tree is explored).  This might be possible.

If you're not interested in coding, then I don't think there will be a
very good solution until IOS is more developed and integrated with
glpsol.

Brady

-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/