Re[4]: [Help-glpk] glpk 4.5 release information

[Michael Hennebry]

On Wed, 21 Jul 2004, Andrew Makhorin wrote:

> >I am very interested in this, if you have the time.
>
> You should modify the file glpmip2.c as follows:
>
> 881   /* check if the time limit has been exhausted */
> 882   if (tree->tm_lim >= 0.0 && tree->tm_lim <= utime() - tree->tm_beg)
> 883   {  if (tree->msg_lev >= 3)
> 884         print("Time limit exceeded; search terminated");
> 885      ret = MIP_E_TMLIM;
> 886      goto done;
> 887   }
>       /* additional termination tests should go here */
>       if (tree->found && tree->best <= desired_value)
>       {  print something, if needed;
>          ret = MIP_E_TMLIM;

Why not a value indicating OK?

>          goto done;
>       }
> 888   /* display current progress of the search */

My recollection is that there is a parameter
that would do almost exactly what was requested.
At one time it was called LPX_K_TOLOBJ.
An upper bound of 10**-3 was enforced.
Editing the code to raise that bound should
allow the user to specify a 10% rule.

I gathered from reading the code that it was intended to
deal with the vagaries of finite precision arithmetic,
but it should allow one to settle for a not quite optimum.

Of course the method specified is a bit more flexible.

> tree->found is a flag which being set indicates that at least one
> integer feasible solution has been found.
>
> tree->best is the objective value for the best known integer feasible
> solution (it is undefined if the flag tree->found is not set).
>
> If you need to know the current global bound, it can be obtained as
> follows:
>
>       {  int r = mip_pseudo_root(tree);
>          insist(r != 0);
>          insist(tree->slot[r].node != NULL);
>          global_bound = tree->slot[r].bound;
>          ...
>       }

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