[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Bug-glpk] time limit odd case

From: Brady Hunsaker
Subject: [Bug-glpk] time limit odd case
Date: Fri, 27 Oct 2006 17:00:02 -0400
User-agent: Thunderbird (X11/20060501)


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 Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh

reply via email to

[Prev in Thread] Current Thread [Next in Thread]