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

[Philip Warner]

At 12:59 AM 16/04/2004, Michael Hennebry wrote:
> On Thu, 15 Apr 2004, Philip Warner wrote:
> > 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?
>
> Yes.
> If MIP terminates early for any reason,
> it will still let you discover the incumbent solution, if any.
> Look at the status and solution querying functions.

Thanks for the reply; the problem with this is that unlike lpx_simplex, 
calling lpx_integer a second time restarts the process rather than 
continuing it, which makes it costly to just guess an iteration limit.

Also, there is also no way to terminate iterations from a hook procedure 
(eg. print hook), so it's not possible to set ITLIM to -1 then wait for an 
acceptable result and terminate it (which I still think would be nice).


> For your particular case, you can solve the lp relaxation,
> add an already satisfied constraint, warm up the basis,
> and solve the resulting MIP.
> If the first optimal basis is nearly degenerate,
> warming up the basis might not be sufficient.
> You might have to resolve the new lp relaxation
> before solving the MIP.

This interests me, but I don't actually understand it...I can solve the lp 
relaxation (I have to do so before I call lpx_integer), but I am not sure 
what adding an 'already satisfied constraint' etc means. The relaxed LP 
problem has all the constraints (except integer-ness) already defined.

Thanks again for the reply, and feel free to point me at a general LP text 
if that is necessary!



----------------------------------------------------------------
Philip Warner                    |     __---_____
Albatross Consulting Pty. Ltd.   |----/       -  \
(A.B.N. 75 008 659 498)          |          /(@)   ______---_
Tel: (+61) 0500 83 82 81         |                 _________  \
Fax: (+61) 03 5330 3172          |                 ___________ |
Http://www.rhyme.com.au          |                /           \|
                                 |    --________--
PGP key available upon request,  |  /
and from pgp.mit.edu:11371       |/