<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Rudi,<br>
<br>
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.<br>
<br>
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.<br>
<br>
For a quick test, I switched off cuts and did zero nodes - that
took 40 minutes.<br>
<br>
The command passed to Cbc was<br>
cbc test.lp -dualize 1 -sprint 100 -primals -dualize 0 -sprint 0
-primals -cuts off -maxnode 0 -solve<br>
<br>
The initial solve takes two minutes.<br>
<br>
After that you are using the initial formulation.<br>
<br>
Assuming that is the normal shape of your problems, there are two
approaches to making code faster - neither trivial.<br>
<br>
a) after pre-processing turn most of the constraints into
mandatory cuts.<br>
b) derive from OsiClpSolverInterface and make the solves
intelligent enough to dualize problems that look as if it would
help.<br>
<br>
I attach log of my test run.<br>
John Forrest <br>
<br>
On 13/09/16 17:44, Rudi Araújo wrote:<br>
</div>
<blockquote cite="mid:07a101d20dde$090096a0$1b01c3e0$@siscog.pt"
type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=iso-8859-1">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-GB">Hi,</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">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.</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">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:</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">cbc -seconds 14400
-import test.lp -maxNodes 0 -log 3 -solve</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">And the process outputs
the following:</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">Welcome to the CBC MILP
Solver</span></p>
<p class="MsoNormal"><span lang="EN-GB">Version: 2.9</span></p>
<p class="MsoNormal"><span lang="EN-GB">Build Date: Sep 2 2016</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">command line -
Z:\siscog\cbc-2.9\bin\cbc.exe -seconds 14400 -import test.lp
-maxNodes 0 -log 3 -solve (default strategy 1)</span></p>
<p class="MsoNormal"><span lang="EN-GB">seconds was changed from
1e+100 to 14400</span></p>
<p class="MsoNormal"><span lang="EN-GB">maxNodes was changed
from 2147483647 to 0</span></p>
<p class="MsoNormal"><span lang="EN-GB">logLevel was changed
from 1 to 3</span></p>
<p class="MsoNormal"><span lang="EN-GB">Continuous objective
value is 12360 - <b>98540.20</b> seconds</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0006I 80 SOS (17507
members out of 84939) with 17507 overlaps - too much overlap
or too many others</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0002I 2740 variables
fixed</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0010I element in row
1092 for column 14740 changed from 60000 to 3194</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0010I element in row
1092 for column 14741 changed from 60000 to 3194</span></p>
<p class="MsoNormal"><span lang="EN-GB">...</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0010I element in row
6795 for column 86500 changed from 60000 to 3689</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0009I 227869 elements
changed</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 509271 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 485426 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 461291 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 436698 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 413801 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 390727 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 368252 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 345562 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0003I 0 fixed, 0
tightened bounds, 324250 strengthened rows, 0 substitutions</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cgl0004I processed model
has 337921 rows, 86501 columns (79703 integer (79703 of
which binary)) and 4943399 elements</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cutoff increment
increased from 1e-005 to 0.00999</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cbc0020I Exiting on
maximum time</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cbc0005I Partial search
- best objective 1e+050 (best possible -128040), took 0
iterations and 0 nodes (98741.26 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cbc0035I Maximum depth
0, 0 variables fixed on reduced cost</span></p>
<p class="MsoNormal"><span lang="EN-GB">Cuts at root node
changed objective from -128040 to -128040</span></p>
<p class="MsoNormal"><span lang="EN-GB">Probing was tried 0
times and created 0 cuts of which 0 were active after adding
rounds of cuts (0.000 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB">Gomory was tried 0 times
and created 0 cuts of which 0 were active after adding
rounds of cuts (0.000 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB">Knapsack was tried 0
times and created 0 cuts of which 0 were active after adding
rounds of cuts (0.000 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB">Clique was tried 0 times
and created 0 cuts of which 0 were active after adding
rounds of cuts (0.000 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB">MixedIntegerRounding2
was tried 0 times and created 0 cuts of which 0 were active
after adding rounds of cuts (0.000 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB">FlowCover was tried 0
times and created 0 cuts of which 0 were active after adding
rounds of cuts (0.000 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB">TwoMirCuts was tried 0
times and created 0 cuts of which 0 were active after adding
rounds of cuts (0.000 seconds)</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">Result - Stopped on time
limit</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">No feasible solution
found</span></p>
<p class="MsoNormal"><span lang="EN-GB">Lower
bound: -128040.000</span></p>
<p class="MsoNormal"><span lang="EN-GB">Enumerated
nodes: 0</span></p>
<p class="MsoNormal"><span lang="EN-GB">Total iterations:
0</span></p>
<p class="MsoNormal"><span lang="EN-GB">Time (CPU
seconds): 98743.25</span></p>
<p class="MsoNormal"><span lang="EN-GB">Time (Wallclock
seconds): 98743.25</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">Total time (CPU
seconds): 98751.52 (Wallclock seconds):
98751.52</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">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.)</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">By means of profiling
(using </span><span lang="EN-GB">gprof</span><span
lang="EN-GB">; 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.</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">I have tried the
following:</span></p>
<p class="MsoListParagraph"><span lang="EN-GB"><span>·<span>
</span></span></span><span lang="EN-GB">Turning
preprocessing off; didn't seem to help.</span></p>
<p class="MsoListParagraph"><span lang="EN-GB"><span>·<span>
</span></span></span><span lang="EN-GB">Based on some
notes I found on the web
(<a class="moz-txt-link-freetext" href="http://www.fastercoin.com/f2_files/naqs.html">http://www.fastercoin.com/f2_files/naqs.html</a>) about how to
deal with degeneracy, I tried the idiot heuristic, as
suggested, but to no avail.</span></p>
<p class="MsoListParagraph"><span lang="EN-GB"><span>·<span>
</span></span></span><span lang="EN-GB">Running CLP over
the LP, confirming that all the time is spent in solving the
relaxation.</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">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.</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">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).</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">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).</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">You can find the
offending LP here:
<a class="moz-txt-link-freetext" href="https://drive.google.com/open?id=0B-5kPpSmX5imendFcUhiYlNqelE">https://drive.google.com/open?id=0B-5kPpSmX5imendFcUhiYlNqelE</a></span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">If you could offer some
hints as to what might be the possible causes, and
corresponding solutions, we would be much obliged.</span></p>
<p class="MsoNormal"><span lang="EN-GB"> </span></p>
<p class="MsoNormal"><span lang="EN-GB">Thank you in advance,</span><span
lang="EN-GB"><br>
Rudi Araújo <br>
</span><span lang="EN-GB">Software Engineer </span><span
lang="EN-GB"><br>
<br>
</span><b><span lang="EN-GB">SISCOG - Sistemas Cognitivos, SA</span></b><span
lang="EN-GB"> <br>
</span><span lang="EN-GB">Campo Grande, 378 - 3º, 1700-097
Lisboa • Portugal <br>
Tel: +351 217 529 100 • Fax: +351 217 529 101<br>
</span><span lang="EN-GB"><br>
<br>
</span><span><a moz-do-not-send="true"
href="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="><b><span
lang="EN-GB">www.siscog.pt</span></b></a></span><span
lang="EN-GB"> <br>
<br>
</span><b><span lang="EN-GB">"Optimising the resources of the
world"</span></b><span lang="EN-GB"> <br>
<br>
</span><span lang="EN-GB">DISCLAIMER<br>
This message may contain confidential information. You
should not copy or address this message to third parties.<br>
If you are not the appropriate recipient we kindly ask you
to delete the message and notify the sender.<br>
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. <br>
<br>
</span><span>AVISO<br>
Esta mensagem pode conter informação considerada
confidencial, não devendo ser copiada ou endereçada a
terceiros.<br>
Se o receptor não for o destinatário apropriado, agradecemos
que destrua a mensagem e informe o emissor do sucedido.<br>
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.</span></p>
<p class="MsoNormal"> </p>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Clp mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Clp@list.coin-or.org">Clp@list.coin-or.org</a>
<a class="moz-txt-link-freetext" href="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=">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=</a>
</pre>
</blockquote>
<p><br>
</p>
</body>
</html>