[Scip] SCIP Time Limit Bug

[Bahador Bakhshi]

Dear All,

I think that there is a bug in "time limit" handling in scip. If the
specified time (total solution time) is over in solving LP of a node, scip
will continue in forever loop. As an example, when I tried to solve a LP
model using scip and I limited the solving time (using time_limit.set
setting file), I got the following output:

------------------------------------------------
SCIP version 1.1.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP
solver: SoPlex 1.4.0]
Copyright (c) 2002-2008 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin
(ZIB)

reading user parameter file <time_limit.set>

read problem <throughput_LP.lp>
============

original problem has 3870 variables (0 bin, 0 int, 0 impl, 3870 cont) and
1793 constraints

solve problem
=============

presolving:
...
presolved problem has 3870 variables (0 bin, 0 int, 0 impl, 3870 cont) and
1631 constraints
   1631 constraints of type <linear>
Presolving Time: 0.25

 time | node  | left  |LP iter| mem |mdpt |frac |vars |cons |ccons|cols
|rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
  2.3s|     1 |     0 |  1896 |  20M|   0 |   - |3870 |1631 |1631 |3870
|1631 |   0 |   0 |   0 | 4.000000e+02 |      --      |    Inf
  2.3s|     1 |     0 |  1896 |  20M|   0 |   - |3870 |1631 |1631 |3870
|1631 |   0 |   0 |   0 | 4.000000e+02 |      --      |    Inf
  ...
  2.6s|     1 |     0 |  1896 |  20M|   0 |   - |3870 |1631 |1631 |3870
|1631 |   0 |   0 |   0 | 4.000000e+02 |      --      |    Inf
  2.6s|     1 |     0 |  1896 |  20M|   0 |   - |3870 |1631 |1631 |3870
|1631 |   0 |   0 |   0 | 4.000000e+02 |      --      |    Inf
  2.6s|     1 |     0 |  1896 |  20M|   0 |   - |3870 |1631 |1631 |3870
|1631 |   0 |   0 |   0 | 4.000000e+02 |      --      |    Inf
  2.6s|     1 |     0 |  1896 |  20M|   0 |   - |3870 |1631 |1631 |3870
|1631 |   0 |   0 |   0 | 4.000000e+02 |      --      |    Inf
  2.6s|     1 |     0 |  1896 |  20M|   0 |   - |3870 |1631 |1631 |3870
|1631 |   0 |   0 |   0 | 4.000000e+02 |      --      |    Inf
------------------------------------------------

The time_limit.set setting file contains only one setting:
------------------------------------------------
# maximal time in seconds to run
# [type: real, range: [0,1.79769313486232e+308], default: 1e+20]
limits/time = 2
------------------------------------------------

After some debugging, I found that scip does NOT terminate if the LP solving
is interrupted due to time limit. For example, in my problem, I set the time
limit to 2, but scip continues in 2.6sec.

I did a workaround about the bug and scip is working fine now; but I am not
sure this is the best solution. My workaround patch is as following:
------------------------------------------------
--- old/scip-1.1.0/src/scip/solve.c 2008-11-06 15:48:11.000000000 +0000
+++ new/scip-1.1.0/src/scip/solve.c 2008-11-06 15:51:43.000000000 +0000
@@ -2461,6 +2461,9 @@
          if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ||
SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT )
             SCIPtreeSetFocusNodeLP(tree, FALSE);

+         if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT )
+                 return SCIP_OKAY;
+
          /* if we solve exactly, the LP claims to be infeasible but the
infeasibility could not be proved,
           * we have to forget about the LP and use the pseudo solution
instead
           */
@@ -2989,6 +2992,10 @@
       /* solve focus node */
       SCIP_CALL( solveNode(blkmem, set, stat, prob, primal, tree, lp,
pricestore, sepastore, branchcand, cutpool,
             conflict, eventfilter, eventqueue, &cutoff, &unbounded,
&infeasible, restart, &afternodeheur) );
+
+       if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT )
+             return SCIP_OKAY;
+
       assert(!cutoff || infeasible);
       assert(SCIPbufferGetNUsed(set->buffer) == 0);
       assert(SCIPtreeGetCurrentNode(tree) == focusnode);
------------------------------------------------


Best Regards.
---Bahador.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20081106/c18c9f46/attachment.html