[Clp] Help with CLP: linear relaxation taking too long
John Forrest
john.forrest at fastercoin.com
Sun Sep 18 04:52:14 EDT 2016
Rudi,
Getting the LP solved faster was not too hard, but I noticed a bug in
preprocessing which had to be fixed (committed to stable and trunk). I
will be looking to see if anything is wrong with normal solve - 300K
iterations seems a bit too much.
The problem has many more rows than columns so the dual of the problem
is much easier. There is a dualize option which needs to be treated
carefully e.g. switch off as soon as possible. As the dual has many more
columns than rows then the "sprint" method works well. The code may
choose that option anyway, but is is safer to choose it explicitly.
For a quick test, I switched off cuts and did zero nodes - that took 40
minutes.
The command passed to Cbc was
cbc test.lp -dualize 1 -sprint 100 -primals -dualize 0 -sprint 0
-primals -cuts off -maxnode 0 -solve
The initial solve takes two minutes.
After that you are using the initial formulation.
Assuming that is the normal shape of your problems, there are two
approaches to making code faster - neither trivial.
a) after pre-processing turn most of the constraints into mandatory cuts.
b) derive from OsiClpSolverInterface and make the solves intelligent
enough to dualize problems that look as if it would help.
I attach log of my test run.
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/20160918/873a0b76/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.log
Type: text/x-log
Size: 20346 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/clp/attachments/20160918/873a0b76/attachment-0001.bin>
More information about the Clp
mailing list