[Bug-glpk] time limit odd case

[Brady Hunsaker]

Andrew,

My student and I noticed some incorrect behavior (in our opinion) for 
the time limit parameter.  When solving a MILP, the time limit is only 
checked while solving the root LP relaxation and then before solving 
each node in the b&b tree.

We came across an odd case where one of the nodes takes a long time to 
solve (maybe it's even a numerical issue).  At any rate, the time limit 
does not work correctly, because it isn't checked until after the node 
is solved.

A quick fix is to add a single line at around line 736 of glpmip1.c in 
function mip_solve_node():
      lpx_set_real_parm(lp, LPX_K_TMLIM, tree->tm_lim + tree->tm_beg - 
utime());

This just passes a time limit to the LP algorithm.  We tried this and it 
 seems to work OK, though we haven't yet recreated the real problem 
situation.

This solution isn't quite correct, because some time passes between the 
last check and this check, so the value above could actually be 
negative.  If that were the case, it wouldn't work correctly.  Better 
would be something like:

      double remaining_time;

      remaining_time = tree->tm_beg + tree->tm_lim - utime();
      /* Check that there is always a small positive limit */
      if (tree->tm_lim > 0 && remaining_time <= 0.0)
          remaining_time = 0.1;
      lpx_set_real_parm(lp, LPX_K_TMLIM, remaining_time);

I haven't tested that, though.

Brady

--
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/