[Coin-discuss] Infinite loop in preprocessing / CBC

[John J Forrest]

Torsten,

Send the file to me.

John Forrest



<Torsten.Fahle at inform-ac.com> 
Sent by: coin-discuss-bounces at list.coin-or.org
09/13/2006 11:22 AM
Please respond to
Discussions about open source software for Operations Research 
<coin-discuss at list.coin-or.org>


To
<coin-discuss at list.coin-or.org>
cc

Subject
[Coin-discuss] Infinite loop in preprocessing / CBC






Hi all,

I've run into a strange behavior of ./cbc on one of our MPS files. 
Applying CBC to that file with preprocess switched on CBC runs in an 
"infinite" loop during integer preprocess.
The following message appears again and again (well after 10 minutes I 
stopped that run):

    Coin0510I Presolve is modifying 1 integer bounds and re-presolving

Without preprocess an optimal integer solution is found within a fraction 
of a second(!)


The source of the message is OsiPresolve::presolvedModel(...) in 
OsiPresolve.cpp where any tightening 
of some integer bound indeed triggers a new presolving.
Further debugging showed that it is always the same variable (C0000031) 
for which this message occurs
Initially, the lower bound of that variable is set to 0 and increased to 1 
in the first iteration in presolvedModel(..)
Next iteration increases it to 2, then to 3, 4,5,6,7 etc. Since this 
variable is unbounded (UI 1e30 in the MPS file) 
that process may run for some time.

So I manipulated the bounds in the MPS file. If variable C00031 is fixed 
to some value, there is no problem.
In both cases (presolve on / off) an optimal integer solution is found 
quickly.
Interestingly, if I decrease the upper bound of that variable from UI 1e30 
to UI 1e25 or below the problem also disappears,
whereas UI 1e26 and above reproduce the problem. Maybe this is some hint 
on a numerical problem?

The problem in cbc from coin_all_2006Sept13.tgz on our mps file. 
The zipped mps file has 78Kb which is more than the allowed mail size for 
this list. 
Anyone interested can contact me and will get the file directly.

Using that file, the problem can be reproduced as follows:
  Cbc/Src/cbc -log 5 -slog 5 -import problem.mps -preprocess on -branch

switching -preprocess off shows that the file can be solved quickly.

The same problem also appears in some older code (COIN CVS version of 
April, 28th 2006)
My platforms are AMD Athlon XP running Linux (g++ 3.3.4) and Windows XP + 
Microsoft Visual Studio 2003.

Any hints on what's going on here? 

Thanks a lot,

   Torsten

---
Dr. Torsten Fahle
Geschäftsbereich Systeme Airport
INFORM GmbH, Pascalstr.23, 52076 Aachen, Germany
Tel. (+49) 24 08 - 94 56 24  FAX: -94 56 25
e-mail: Torsten.Fahle at inform-ac.com   http://www.groundstar.de 




_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060913/6c877b79/attachment.html>