Re: [Help-glpk] binary variables writing lp format; and MIP bounds

[Brady Hunsaker]

On Wed, 2004-08-11 at 17:03, Andrew Makhorin wrote:
<snip>
> >2.  IOS seems much better than the previous branch-and-bound solver.  I
> >would like to improve the LP bound, however.
> 
> If you mean mip_driver, it uses its own data structures, not IOS
> (although these data structures is a simplified version of IOS which
> does not allow adding/deleting rows and columns).
> 

I was confused and thought that IOS was being used.  Nevertheless, I
like the simplified version of IOS that is being used.  It opens up new
opportunities for improvements, like the one below.

> >  At present, the LP bound
> >at the pseudo-root is used.  In fact, the maximum (or minimum) of the LP
> >bounds at active nodes could be used and reported.  I would like to add
> >this change as well as including a standard option for specifying an
> >integrality gap for termination of the algorithm.  Is there any reason
> >not to do this?
> >
> >If there's no obvious reason not to, then I'll work on these changes and
> >send them in,
> 
> What does "the maximum/minimum of the LP bounds at active nodes could be
> used and reported" mean? Used for what? Please explain.
> 

Assume that the problem is maximization.  Then the maximum of the LP
bounds at active nodes is an upper bound on the true optimal solution
value.  Currently, GLPK uses the LP bound at the pseudo-root, which is a
valid upper bound, but may be higher than the maximum of the active
nodes.

Checking the active nodes takes slightly more time, but I believe is
worth it.  I'll send you my sample code that makes the changes.

Brady