[Coin-discuss] Infinite loop in preprocessing / CBC
Torsten.Fahle at inform-ac.com
Torsten.Fahle at inform-ac.com
Tue Sep 19 10:10:04 EDT 2006
John,
Ups, seems that I missed that one while checking the HEAD. Sorry!
I included that fix as well. Now it works perfectly.
Thanks a lot!
Torsten
>>> On 19.09.2006 at 15:54, in message
<OF4CCFBAED.62DFD522-ON852571EE.004C3AF0-852571EE.004C5CF0 at us.ibm.com>, John J
Forrest <jjforre at us.ibm.com> wrote:
> 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
>
>
>
> _______________________________________________
> 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