[Top][All Lists]

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

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

From: Philip Warner
Subject: Re: [Help-glpk] Using MIP to get a less-than-optimal solution?
Date: Fri, 16 Apr 2004 13:53:16 +1000

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?

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://          |                /           \|
                                 |    --________--
PGP key available upon request,  |  /
and from |/

reply via email to

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