[Cbc] wrong optimal solution - preprocess SOS - preprocess aggregate works fine
John Forrest
jjhforrest at gmail.com
Fri Jan 24 12:54:14 EST 2020
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
>
More information about the Cbc
mailing list