[Clp] Help with CLP: linear relaxation taking too long
John Forrest
john.forrest at fastercoin.com
Thu Sep 15 02:10:12 EDT 2016
Rudi,
Will look into it (slowly).
John Forrest
On 13/09/16 17:44, Rudi Araújo wrote:
>
> Hi,
>
> We have been using CBC lately for some experiments at SISCOG, and
> despite some bumps along the way, the experience generally has been
> going smoothly. However, we have stumbled upon a situation that we are
> having trouble understanding, and wondered if you might be so kind as
> to give us a helping hand.
>
> The situation is the following: we have created an LP that is
> apparently choking CBC. What I mean with this is that CBC doesn't even
> start doing its normal business (cuts, B&B): it apparently gets stuck
> in solving the relaxation. I say this because I run the optimiser as
> follows:
>
> cbc -seconds 14400 -import test.lp -maxNodes 0 -log 3 -solve
>
> And the process outputs the following:
>
> Welcome to the CBC MILP Solver
>
> Version: 2.9
>
> Build Date: Sep 2 2016
>
> command line - Z:\siscog\cbc-2.9\bin\cbc.exe -seconds 14400 -import
> test.lp -maxNodes 0 -log 3 -solve (default strategy 1)
>
> seconds was changed from 1e+100 to 14400
>
> maxNodes was changed from 2147483647 to 0
>
> logLevel was changed from 1 to 3
>
> Continuous objective value is 12360 - *98540.20* seconds
>
> Cgl0006I 80 SOS (17507 members out of 84939) with 17507 overlaps - too
> much overlap or too many others
>
> Cgl0002I 2740 variables fixed
>
> Cgl0010I element in row 1092 for column 14740 changed from 60000 to 3194
>
> Cgl0010I element in row 1092 for column 14741 changed from 60000 to 3194
>
> ...
>
> Cgl0010I element in row 6795 for column 86500 changed from 60000 to 3689
>
> Cgl0009I 227869 elements changed
>
> Cgl0003I 0 fixed, 0 tightened bounds, 509271 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 485426 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 461291 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 436698 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 413801 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 390727 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 368252 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 345562 strengthened rows, 0
> substitutions
>
> Cgl0003I 0 fixed, 0 tightened bounds, 324250 strengthened rows, 0
> substitutions
>
> Cgl0004I processed model has 337921 rows, 86501 columns (79703 integer
> (79703 of which binary)) and 4943399 elements
>
> Cutoff increment increased from 1e-005 to 0.00999
>
> Cbc0020I Exiting on maximum time
>
> Cbc0005I Partial search - best objective 1e+050 (best possible
> -128040), took 0 iterations and 0 nodes (98741.26 seconds)
>
> Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
>
> Cuts at root node changed objective from -128040 to -128040
>
> 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)
>
> Result - Stopped on time limit
>
> No feasible solution found
>
> Lower bound: -128040.000
>
> Enumerated nodes: 0
>
> Total iterations: 0
>
> Time (CPU seconds): 98743.25
>
> Time (Wallclock seconds): 98743.25
>
> Total time (CPU seconds): 98751.52 (Wallclock seconds): 98751.52
>
> As you can see, it took more than 27 hours (way above the given time
> limit of 4 hours), and it didn't even try any cuts at the root node.
> And, by the way, the execution time is quite variable: I've seen it
> take 12h, 15h, and 17h on different occasions, though using an
> unstable version. (I don't think this is due to using the computer
> simultaneously with the CBC run, since I'm running on a multiple core
> CPU, and CBC is pretty much running on its dedicated core.)
>
> By means of profiling (using gprof; see the result attached), I have
> come to some faint conclusion that dualizing the problem is what's
> costing these much CPU cycles, but we have no hint on how to pursue
> further with the analysis.
>
> I have tried the following:
>
> ·Turning preprocessing off; didn't seem to help.
>
> ·Based on some notes I found on the web
> (http://www.fastercoin.com/f2_files/naqs.html) about how to deal with
> degeneracy, I tried the idiot heuristic, as suggested, but to no avail.
>
> ·Running CLP over the LP, confirming that all the time is spent in
> solving the relaxation.
>
> I have also ruled out the sheer size of the problem (~100.000
> variables; ~1.000.000 constraints) as a possible cause, since we have
> been solving larger LPs, and with a similar variable/constraints ratio.
>
> Another possibly important note: I have, on other occasions,
> experienced the same problem with other LPs, but the one I send you is
> the only one that appears to cause this problem consistently, while
> the others appeared to cause it non-deterministically, which might
> indicate that the problem is indeed rooted in some non-deterministic
> component (such as perturbation).
>
> We have found that the LP is feasible and that the optimal solution
> has objective 12360.0 (which, by the way, is also the objective of the
> relaxation).
>
> You can find the offending LP here:
> https://drive.google.com/open?id=0B-5kPpSmX5imendFcUhiYlNqelE
>
> If you could offer some hints as to what might be the possible causes,
> and corresponding solutions, we would be much obliged.
>
> Thank you in advance,
> Rudi Araújo
> Software Engineer
>
> *SISCOG - Sistemas Cognitivos, SA*
> Campo Grande, 378 - 3º, 1700-097 Lisboa • Portugal
> Tel: +351 217 529 100 • Fax: +351 217 529 101
>
>
> *www.siscog.pt*
> <https://urldefense.proofpoint.com/v2/url?u=http-3A__www.siscog.pt&d=CwMFAw&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=bdDqA0BRlyQIiqvl6NgNGovCKLQNnaPTKUW2NwyBcN0&s=LLOeYkPVaiW0gSIUuy2hK2zhKsRxPAciKVddVtSYW48&e=>
>
> *"Optimising the resources of the world"*
>
> DISCLAIMER
> This message may contain confidential information. You should not copy
> or address this message to third parties.
> If you are not the appropriate recipient we kindly ask you to delete
> the message and notify the sender.
> The contents of this message and its attachments are the sole
> responsibility of the sender and under no circumstances can SISCOG -
> Sistemas Cognitivos, SA be liable for any resulting consequences.
>
> AVISO
> Esta mensagem pode conter informação considerada confidencial, não
> devendo ser copiada ou endereçada a terceiros.
> Se o receptor não for o destinatário apropriado, agradecemos que
> destrua a mensagem e informe o emissor do sucedido.
> O conteúdo desta mensagem bem como dos respectivos anexos é da
> responsabilidade exclusiva do emissor, não podendo a SISCOG - Sistemas
> Cognitivos, SA ser responsabilizada por eventuais consequências.
>
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=bdDqA0BRlyQIiqvl6NgNGovCKLQNnaPTKUW2NwyBcN0&s=gYO0CzOdhADQ54zH9uV7m5mFjk7_AClMdBUhxNvI7i0&e=
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20160915/760bd550/attachment.html>
More information about the Clp
mailing list