[Coin-discuss] Infinite loop in preprocessing / CBC
John J Forrest
jjforre at us.ibm.com
Tue Sep 19 09:54:45 EDT 2006
Torsten,
That 100 loop check was just an extra. The bug fix was to
CoinPresolveDupcol.cpp.
John
<Torsten.Fahle at in
form-ac.com>
Sent by: To
coin-discuss-boun "Discussions about open source
ces at list.coin-or. software for Operations Research"
org <coin-discuss at list.coin-or.org>
cc
09/19/06 09:21 AM Subject
Re: [Coin-discuss] Infinite loop in
preprocessing / CBC
Please respond to
Discussions about
open source
software for
Operations
Research
<coin-discuss at lis
t.coin-or.org>
Dear John,
Thanks for your effort. And sorry for my late reply - I was out of office
the last days.
Unfortunately, there is still a problem. Now the problem is not solved to
optimality.
I tried with the two most recent tarballs: coin_all_2006Sept18.tgz and
coin_all_2006Sept19.tgz
Both show the same behavior as the old tarball of September, 13th.
I assume the tarballs do not contain the development branch.
So I checked with the subversion HEAD and found that Changeset 794 ("fix
presolve bug",
09/14/06 14:14:29) is probably the correction for the problem.
The only file involved is branches/devel/Osi/src/OsiPresolve.cpp. The new
element is a counter
that prevents presolving from iterating more than 100 times.
I included these changes into the files from the tarball.
This obviously stops preprocessing from looping again and again. The final
objective value,
however, is different from the objective value when not using preprocessing
(227208 vs. 179202,
the later one is also the value found by CPLEX).
* preprocess OFF: ./cbc -import problem.mps -preprocess off branch
Problem BLANK has 2048 rows, 1912 columns and 22025 elements
Model was imported from problem.mps in 0.029995 seconds
Option for preprocess changed from sos to off
Optimal - objective value 179202
Optimal - objective value 179202
1908 integer variables and 4 variables could be made integer
Cbc0009I Objective coefficients multiple of 2.5
cutoff increment increased from 1e-05 to 2.4975
Cuts at root node changed objective from 179202 to 179202
[ ... ]
Result - Finished objective 179202 after 0 nodes and 0 iterations - took
0.059991 seconds
* preprocess ON: ./cbc -import problem.mps -preprocess on branch
Problem BLANK has 2048 rows, 1912 columns and 22025 elements
Model was imported from problem.mps in 0.025996 seconds
Option for preprocess changed from sos to on
Optimal - objective value 179202
processed model has 1985 rows, 1881 columns and 20914 elements
Optimal - objective value 227208
1881 integer variables
Cbc0009I Objective coefficients multiple of 2.5
cutoff increment increased from 1e-05 to 2.4975
Cuts at root node changed objective from 227208 to 227208
[...]
Result - Finished objective 227208 after 0 nodes and 0 iterations - took
2.79058 seconds
My interpretation:
If we stop preprocessing after 100 iterations, the lower bound of variable
C0000031 99.
That is also the value of that variable in the solution claimed optimal
when using preprocessing.
(Variable C0000031 is the one for which the infinity loop occurred in the
older versions)
In the optimal solution found without preprocessing, however, that variable
has a value of 1.0. Moreover, if that variable is
fixed to some larger value the optimal objective value increases.
So apart from the looping there must be another numerical or logical
problem in the code,
as increasing the variable does impact on optimality,
whereas preprocessing assumes that tightening the bounds of C0000031 is
fine.
Thanks again,
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
>>> On 15.09.2006 at 23:20, in message
<OF0197CA68.B80B0617-ON852571EA.00752F7A-852571EA.007533F2 at us.ibm.com>,
John J
Forrest <jjforre at us.ibm.com> wrote:
> Hopefully should be fixed.
>
>
>
> <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
_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss
More information about the Coin-discuss
mailing list