[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 1.5.0.2 (X11/20060501) |

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/

**[Bug-glpk] time limit odd case**,
*Brady Hunsaker* **<=**