[Help-glpk] MIP Qestion

[Huegler, Peter A.]

I have successfully coded a MIP problem that the branch and bound routines
in GLPK can solve.  Now I want to speed up the solution time.  I have an
upper bound to my MIP problem generated from a heuristic.  I want to use
this upper bound to fathom branches within GLPK.  I have successfully added
a two integer parameters for the external upper bound.  The first parameter
(called extub_flag) identifies whether an upper is set and the second
parameter (called extub) is the actual upper bound value.  Both of these
parameters are available in the bbm1_cp structure.

Now my question is where do I add the upper bound check to fathom branches?
I have tracked down two places in glpbbm.c to add changes.  The first is in
bbm1_driver.  The new code is as follows:

      if (bb->found)
      {  if (check_rr(node->objval, bb->best, cp->tol_obj) >= -1)
            goto cut;
      }
      else
      {  if ( cp->extub_flag )
         {  if (check_rr(eval_objfun(), cp->extub, cp->tol_obj) >= -1)
               goto cut;
         }
      }

The second place is in dual_monit and the new code is as follows:

      if (bb->found)
      {  eval_bbar(bb->rsm, bb->bbar);
         if (check_rr(eval_objfun(), bb->best, cp->tol_obj) >= -1)
         {  why = 0;
            ret = 1;
         }
      }
      else
      {  if ( cp->extub_flag )
         {
            double pah_a;
            pah_a = eval_objfun();
            if (check_rr(eval_objfun(), cp->extub, cp->tol_obj) >= -1)
            {  why = 0;
               ret = 1;
            }
         }
      }

These changes appear to fathom branches too early and the MIP result is no
feasible integer solution (although there is one without checking the upper
bound).  What is it that I am missing?

Thanks in advance for any help.

Pete



Peter A. Huegler
Supervisor
Systems Analysis Group
Homer Research Labs
Bethlehem Steel
Bethlehem, PA 18016

Phone:  8-232-4972              (BethComNet)
        (610) 694-4972          (Outside)