[Coin-discuss] Infinite loop in preprocessing / CBC

[Torsten.Fahle at inform-ac.com]

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