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

[Michael Hennebry]

On Fri, 16 Apr 2004, Philip Warner wrote:

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

If you've run out of time, you wouldn't want to restart.

Something you could do is to start with a small iteration limit
and double it for each successive run until you get what you want.

> 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).

If you have a hook procedure,
perhaps you could adjust the pivot count or the limit.

> >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

> > > integer solution that is at most 20% more expensive, can I use MIP to

Add
cost <= 1.2 lpcost
to the lp and fix the basis before calling lpx_integer

-- 
Mike   address@hidden
"Nothing says it like words if you know how to use them."
                        --  the Professional Organization of English Majors