[Cbc] wrong optimal solution - preprocess SOS - preprocess aggregate works fine
John Forrest
jjhforrest at gmail.com
Tue Jan 28 12:55:10 EST 2020
Pieter,
There seems to be a minor bug in that the time spent before entering
Branch and Bound counts twice against the maximum time limit! So time
in solving it was less than 600 seconds - just 460 Cpu seconds which is
not a lot. Problem still has 23000 rows after preprocessing so is not
going to solve very quickly.
I have tried a local fix for time problem (needs a bit more thinking to
make some printout better) just solved normally giving ratiogap of 0.001
and 1500 seconds elapsed with 4 cores.
I had 710059 as solution at root node and 382785 at end.
Probably you should look at some of the examples using the event handler
to decide when to stop - as that would give you greater control.
John Forrest
On 27/01/2020 09:37, Pieter Zieschang wrote:
> Hi John,
>
> Presolve=SOS is working now for most problems i have.
>
> Except this one
> https://mega.nz/#!pvwDCC4A!GQBkhIZxkTdYaasgv_zGJwtIa1xQnWA98zisqsb2G-Q
>
>
> Seems like it didn't find any solution at all?
> Maybe my parameters are too bad.
>
>
> /opt/msp/cbc-trunk-2020-01-24/bin/cbc 23844-T1_0.mps timemode=elapsed
> -seconds=600 -keepNames=on -threads=8 -dualt=1e-06 -perturb=on
> -pertvalue=61 -constraint=on -cuts=on -clique=forceon -zero=forceon
> -probing=forceonstrong -combine=on -combine2=on -ratiogap=0.001
> -multiple=8 -preprocess=sos -solve
>
> ...
>
> Cbc0012I Integer solution of 1.0045498e+09 found by Multiple root
> solvers after 0 iterations and 0 nodes (334.98 seconds)
> Cbc0030I Thread 0 used 0 times, waiting to start 0.54918051, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Thread 1 used 0 times, waiting to start 0.48254895, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Thread 2 used 0 times, waiting to start 0.41087604, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Thread 3 used 0 times, waiting to start 0.34028697, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Thread 4 used 0 times, waiting to start 0.27142525, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Thread 5 used 0 times, waiting to start 0.20406055, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Thread 6 used 0 times, waiting to start 0.13375831, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Thread 7 used 0 times, waiting to start 0.064822912, 0 cpu
> time, 0 locks, 0 locked, 0 waiting for locks
> Cbc0030I Main thread 0 waiting for threads, 1 locks, 1.1205673e-05
> locked, 2.1457672e-06 waiting for locks
> Cbc0020I Exiting on maximum time
> Cbc0005I Partial search - best objective 1.0045498e+09 (best possible
> 376997.5), took 0 iterations and 0 nodes (335.73 seconds)
> Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
> Cuts at root node changed objective from 376997 to 376997
> Probing was tried 0 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.000 seconds)
> Gomory was tried 0 times and created 0 cuts of which 0 were active after
> adding rounds of cuts (0.000 seconds)
> Knapsack was tried 0 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.000 seconds)
> Clique was tried 0 times and created 0 cuts of which 0 were active after
> adding rounds of cuts (0.000 seconds)
> MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0
> were active after adding rounds of cuts (0.000 seconds)
> FlowCover was tried 0 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.000 seconds)
> TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.000 seconds)
> ZeroHalf was tried 0 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.000 seconds)
>
> Result - Stopped on time limit
>
> Objective value: 1004549786.00000000
> Lower bound: 376997.500
> Gap: 2663.61
> Enumerated nodes: 0
> Total iterations: 0
> Time (CPU seconds): 459.71
> Time (Wallclock seconds): 341.82
>
> Total time (CPU seconds): 460.09 (Wallclock seconds): 342.24
>
>
> Thank you
>
>
> Mit freundlichen Grüßen / Kind regards
> ________________________________________
>
> *Pieter Zieschang*
>
> *Modis IT Outsourcing GmbH*
> Atriumstraße 1, 04315 Leipzig
>
> Amtsgericht Düsseldorf: HRB 78227
> Geschäftsführer: Martin Wimmer, Jörg Brinkmann
>
> ito.modis.de <https://ito.modis.de/>
>
>
>
>
>
>
> From: "John Forrest" <jjhforrest at gmail.com>
> To: cbc at list.coin-or.org
> Date: 24.01.2020 18:57
> Subject: Re: [Cbc] wrong optimal solution - preprocess SOS - preprocess
> aggregate works fine
> Sent by: "Cbc" <cbc-bounces at coin-or.org>
> ------------------------------------------------------------------------
>
>
>
> Pieter,
>
> I think I have fixed the problem in trunk.
>
> With some options, pre-processing tries to move costs from continuous
> variables to integer variables - and when it does that the offset to the
> objective will change. It does this before presolving the problem.
> Your model has some fixed variables at non-zero values (which would have
> vanished in presolving). There was a section of the code in
> CglPreProcess.cpp which got confused and adjusted the objective incorrectly.
>
> When I ran the problem the solution values produced by the bad code were
> good, but the objective value did not match the correct value.
>
> I have tested the changes on other models - but if anyone finds they
> have problems, add -DSKIP_MOVE_COSTS_TO_INTEGERS to your configure AND
> inform me.
>
> John Forrest
>
>
>
> On 24/01/2020 09:18, Pieter Zieschang wrote:
>> Hi Ted,
>>
>> the version is current trunk, as of January 22th.
>>
>>
>> The problem is available for testing here:
>> https://mega.nz/#!c3Y0CA7R!jFnYcFVzcnYSWucZrCIdgb_AQzE5etB1JlySKom1QuE
>>
>> Command is in the post below.
>>
>>
>> I'm not sure if i make it to opening an issue on github today.
>>
>>
>> Thank you
>>
>>
>> Mit freundlichen Grüßen / Kind regards
>> ________________________________________
>>
>> *Pieter Zieschang*
>>
>> *Modis IT Outsourcing GmbH*
>> Atriumstraße 1, 04315 Leipzig
>>
>> Amtsgericht Düsseldorf: HRB 78227
>> Geschäftsführer: Martin Wimmer, Jörg Brinkmann
>>
>> ito.modis.de <https://ito.modis.de/>
>>
>>
>>
>>
>>
>>
>> From: "Ted Ralphs" <ted at lehigh.edu>
>> To: "Pieter Zieschang" <pieter.zieschang at modis.de>
>> Cc: "cbc" <cbc at list.coin-or.org>
>> Date: 24.01.2020 04:36
>> Subject: Re: [Cbc] wrong optimal solution - preprocess SOS - preprocess
>> aggregate works fine
>> ------------------------------------------------------------------------
>>
>>
>>
>> Hi Pieter,
>>
>> Forgive me if I missed something, but what Cbc version? Could you open
>> an issue on Github?
>>
>> Ted
>>
>> On Thu, Jan 23, 2020 at 5:23 AM Pieter Zieschang
>> <_pieter.zieschang at modis.de_ <mailto:pieter.zieschang at modis.de>> wrote:
>> Hello,
>>
>> there seems to be something going wrong when preprocess=sos (the
>> default) is used, cbc selecting the wrong branch?
>>
>> When preprocess=aggregate the correct optimal solution is found, also
>> solution time is longer, probably the
>>
>>
>> Correct Optimal Solution:
>>
>> $ cbc Problem_25581_0.mps timemode=elapsed -seconds=400 -keepNames=on
>> -threads=8 -dualt=1e-06 -perturb=on -pertvalue=61 -constraint=on
>> -cuts=on -clique=forceon -zero=forceon -probing=forceonstrong
>> -combine=on -combine2=on -ratiogap=0.001 -multiple=8
>> -preprocess=aggregate -solve
>>
>> Cbc0011I Exiting as integer gap of 3.0000005e-05 less than 1e-10 or 0.1%
>> Cbc0001I Search completed - best objective 180.9999999999945, took 1048
>> iterations and 0 nodes (117.76 seconds)
>> Cbc0035I Maximum depth 0, 289 variables fixed on reduced cost
>> Cuts at root node changed objective from 177 to 181
>> Probing was tried 108 times and created 793 cuts of which 0 were active
>> after adding rounds of cuts (1152.645 seconds)
>> Gomory was tried 108 times and created 441 cuts of which 0 were active
>> after adding rounds of cuts (25.991 seconds)
>> Knapsack was tried 108 times and created 18 cuts of which 0 were active
>> after adding rounds of cuts (9.414 seconds)
>> Clique was tried 108 times and created 0 cuts of which 0 were active
>> after adding rounds of cuts (0.226 seconds)
>> MixedIntegerRounding2 was tried 108 times and created 27 cuts of which 0
>> were active after adding rounds of cuts (15.430 seconds)
>> FlowCover was tried 108 times and created 0 cuts of which 0 were active
>> after adding rounds of cuts (6.004 seconds)
>> TwoMirCuts was tried 108 times and created 1530 cuts of which 0 were
>> active after adding rounds of cuts (33.287 seconds)
>> ZeroHalf was tried 108 times and created 27 cuts of which 0 were active
>> after adding rounds of cuts (67.834 seconds)
>>
>> Result - Optimal solution found (within gap tolerance)
>>
>> Objective value: 181.00000000
>> Lower bound: 181.000
>> Gap: 0.00
>> Enumerated nodes: 0
>> Total iterations: 1048
>> Time (CPU seconds): 656.08
>> Time (Wallclock seconds): 121.02
>>
>> Total time (CPU seconds): 656.23 (Wallclock seconds): 121.18
>>
>>
>>
>>
>>
>> Wrong Optimal Solution:
>>
>> $ cbc Problem_25581_0.mps timemode=elapsed -seconds=400 -keepNames=on
>> -threads=8 -dualt=1e-06 -perturb=on -pertvalue=61 -constraint=on
>> -cuts=on -clique=forceon -zero=forceon -probing=forceonstrong
>> -combine=on -combine2=on -ratiogap=0.001 -multiple=8 -solve
>> Cbc0011I Exiting as integer gap of 49802 less than 1e-10 or 0.1%
>> Cbc0001I Search completed - best objective 1200049979, took 0 iterations
>> and 0 nodes (67.05 seconds)
>> Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
>> Cuts at root node changed objective from 1.2e+09 to 1.2e+09
>> Probing was tried 0 times and created 0 cuts of which 0 were active
>> after adding rounds of cuts (0.000 seconds)
>> Gomory was tried 0 times and created 0 cuts of which 0 were active after
>> adding rounds of cuts (0.000 seconds)
>> Knapsack was tried 0 times and created 0 cuts of which 0 were active
>> after adding rounds of cuts (0.000 seconds)
>> Clique was tried 0 times and created 0 cuts of which 0 were active after
>> adding rounds of cuts (0.000 seconds)
>> MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0
>> were active after adding rounds of cuts (0.000 seconds)
>> FlowCover was tried 0 times and created 0 cuts of which 0 were active
>> after adding rounds of cuts (0.000 seconds)
>> TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active
>> after adding rounds of cuts (0.000 seconds)
>> ZeroHalf was tried 0 times and created 0 cuts of which 0 were active
>> after adding rounds of cuts (0.000 seconds)
>> Cgl0014I Postprocessing changed objective from 1.20005e+09 to 49979 -
>> possible tolerance issue - try without preprocessing
>>
>> Result - Optimal solution found (within gap tolerance)
>>
>> Objective value: 1200049979.00000000
>> Lower bound: 1200000177.000
>> Gap: 0.00
>> Enumerated nodes: 0
>> Total iterations: 0
>> Time (CPU seconds): 241.92
>> Time (Wallclock seconds): 72.52
>>
>> Total time (CPU seconds): 242.06 (Wallclock seconds): 72.68
>>
>>
>>
>> Thanks
>>
>>
>>
>>
>>
>> Mit freundlichen Grüßen / Kind regards
>> ________________________________________
>> *
>> Pieter Zieschang*
>> *
>> Modis IT Outsourcing GmbH*
>> Atriumstraße 1, 04315 Leipzig
>>
>> Amtsgericht Düsseldorf: HRB 78227
>> Geschäftsführer: Martin Wimmer, Jörg Brinkmann
>> _
>> __ito.modis.de_ <https://ito.modis.de/>
>>
>>
>> Diese E-Mail und alle Anhänge sind vertraulich und für den Adressaten
>> bestimmt und können auch privilegiert oder von der Offenlegung nach
>> geltendem Recht ausgenommen sein. Wenn Sie nicht der Adressat sind oder
>> diese E-Mail irrtümlicherweise erhalten haben, benachrichtigen Sie den
>> Absender unverzüglich, löschen Sie die E-Mail aus Ihrem System und
>> kopieren Sie keine Teile dieser E-Mail oder deren Anhänge und geben Sie
>> sie nicht weiter.
>>
>> This email and any attachments are confidential and intended for the
>> addressee and may also be privileged or exempt from disclosure under
>> applicable law. If you are not the addressee, or have received this
>> email in error, please notify the sender immediately, delete it from
>> your system and do not copy, or disclose or otherwise act upon any part
>> of this email or its attachments.
>> _______________________________________________
>> Cbc mailing list_
>> __Cbc at list.coin-or.org_ <mailto:Cbc at list.coin-or.org>_
>> __https://list.coin-or.org/mailman/listinfo/cbc_
>>
>>
>> --
>> Dr. Ted Ralphs
>> Professor, Industrial and Systems Engineering
>> Lehigh University
>> (610) 628-1280
>> ted 'at' lehigh 'dot' edu_
>> __coral.ie.lehigh.edu/~ted_ <http://coral.ie.lehigh.edu/~ted>
>>
>> Diese E-Mail und alle Anhänge sind vertraulich und für den Adressaten
>> bestimmt und können auch privilegiert oder von der Offenlegung nach
>> geltendem Recht ausgenommen sein. Wenn Sie nicht der Adressat sind oder
>> diese E-Mail irrtümlicherweise erhalten haben, benachrichtigen Sie den
>> Absender unverzüglich, löschen Sie die E-Mail aus Ihrem System und
>> kopieren Sie keine Teile dieser E-Mail oder deren Anhänge und geben Sie
>> sie nicht weiter.
>>
>> This email and any attachments are confidential and intended for the
>> addressee and may also be privileged or exempt from disclosure under
>> applicable law. If you are not the addressee, or have received this
>> email in error, please notify the sender immediately, delete it from
>> your system and do not copy, or disclose or otherwise act upon any part
>> of this email or its attachments.
>>
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org
>> https://list.coin-or.org/mailman/listinfo/cbc
>>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://list.coin-or.org/mailman/listinfo/cbc
>
>
> Diese E-Mail und alle Anhänge sind vertraulich und für den Adressaten
> bestimmt und können auch privilegiert oder von der Offenlegung nach
> geltendem Recht ausgenommen sein. Wenn Sie nicht der Adressat sind oder
> diese E-Mail irrtümlicherweise erhalten haben, benachrichtigen Sie den
> Absender unverzüglich, löschen Sie die E-Mail aus Ihrem System und
> kopieren Sie keine Teile dieser E-Mail oder deren Anhänge und geben Sie
> sie nicht weiter.
>
> This email and any attachments are confidential and intended for the
> addressee and may also be privileged or exempt from disclosure under
> applicable law. If you are not the addressee, or have received this
> email in error, please notify the sender immediately, delete it from
> your system and do not copy, or disclose or otherwise act upon any part
> of this email or its attachments.
More information about the Cbc
mailing list