[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**: |
Michael Hennebry |

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

**Date**: |
Thu, 15 Apr 2004 09:59:19 -0500 (CDT) |

On Thu, 15 Apr 2004, 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?*
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.
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.
--
Mike address@hidden
"Nothing says it like words if you know how to use them."
-- the Professional Organization of English Majors