<HTML><BODY>
Hi John,<div><br></div><div><span style="background-color: rgb(255, 255, 255); color: rgb(47, 47, 47); font-family: Tahoma, sans-serif; font-size: 14px;">Thank you for your comments</span><span style="background-color: rgb(255, 255, 255);">. </span><span style="background-color: rgb(255, 255, 255); color: rgb(47, 47, 47); font-family: Tahoma, sans-serif; font-size: 14px;">After some help from </span><span style="background-color: rgb(255, 255, 255);">J</span><span style="color: rgb(47, 47, 47); font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">ulian Hall it turned out that my main problem was the presolve - it somehow failed and was followed by primal instead of dual simplex, which seems to be quite slower for my particular problem. Now that this is fixed it seems to be going much faster (still going in hours for the 10 000 size problem, but it's at least tractable), however you raise another very interesting point. </span></div><div><span style="color: rgb(47, 47, 47); font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">I am actually not seeing the mentioned log, so my initial guess is that I should be able to speed things up even more. However, the way I am using the solver (and the only way I am at least partially familiar with it) is like that:</span></div><div><span style="color: rgb(47, 47, 47); font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">1. I have my main project (which is related mostly to the actual generation of the "dense block") in a visual studio project</span></div><div><span style="color: rgb(47, 47, 47); font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">2. I have built the .lib files for the solver from the existing visual studio projects and have linked them to my main project</span></div><div><span style="color: rgb(47, 47, 47); font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">3. I am using the c++ api in the following way:</span></div><div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><div style="padding: 0px; margin: 0px;">ClpSimplex model;</div><div style="padding: 0px; margin: 0px;">// do some stuff related to loading the model from the raw arrays I have generated - loadProblem, etc.</div></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><br style="padding: 0px; margin: 0px;"></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><div style="padding: 0px; margin: 0px;">ClpSolve options;</div><div style="padding: 0px; margin: 0px;">options.setSolveType(ClpSolve::SolveType::useDual);</div><div style="padding: 0px; margin: 0px;">options.setPresolveType(ClpSolve::PresolveType::presolveOff);</div></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><br style="padding: 0px; margin: 0px;"></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">model.initialSolve(options);</div></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><br></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><br></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">Could you please give me some additional details on the following:</div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">1. What changes should I be doing to a visual studio build to replicate the --disable-blas and use_openblas behavior and rebuild the lib files? I can use a 32+ core machine for my experiments, so it should be possible to significantly speed things up if I am able to get this going.</div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">2. Is it possible to use any external implementation for those - for example, I am pretty sure I can get access to Intel's MKL for example, that should be pretty solid in terms of performance. Is that compatible with CLP or the trick works with openblas only ?</div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><br></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">On the other question - I do need the exact solution and I can definitely build a smaller version, however if you can give me tips on the above I prefer to not waste your time additionally and first try to implement the openblas setup and see how it works and maybe after that come back with more information on the problem.</div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><br></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">Thank you very much for your time!</div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);"><br></div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">Best,</div><div style="padding: 0px; margin: 0px; font-family: Tahoma, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);">Ivo</div><div><br><br>
>-------- Оригинално писмо --------
<br> >От: John Forrest john.forrest@fastercoin.com
<br> >Относно: Re: [Clp] question about performance on a strange problem
<br> >До: clp@list.coin-or.org
<br> >Изпратено на: 04.12.2018 16:03
<br><br>
<div class="">
Ivo,
</div>
<div class="">
<br>
</div>
<div class="">
It may not be possible to do much, but here are a few suggestions.
</div>
<div class="">
<br>
</div>
<div class="">
First make sure you have dense factorization switched on. On a typical problem run for a short while with -loglevel 3. You should see output like -
<br>
</div>
<div class="">
<br>
</div>
<div class="">
length of U 24097, length of L 23279 plus 92416 from 304 dense rows
</div>
<div class="">
<br>
</div>
<div class="">
If not then make sure you get Lapack and Blas.
</div>
<div class="">
<br>
</div>
<div class="">
You can do better using openblas - add --disable-blas to configure and add -DCLP_USE_OPENBLAS=1 to CXXDEFS (If dense part very large might even be better to do DCLP_USE_OPENBLAS=4 to use 4 cpus).
</div>
<div class="">
<br>
</div>
<p>If you can send me a smaller version which shows some of the same characteristics, I can look at it and see if there are other approaches. Do you need an exact solution?</p>
<p><br> </p>
<p>John Forrest<br> </p>
<div class="">
<br>
</div>
<div class="">
On 02/12/2018 22:08, Ivo Stefanov wrote:
<br>
</div>
<blockquote>
Hello,
<div>
I am trying to use Clp to solve a linear problem, but it seems to take too long (I have not actually received a solution in several days).
</div>
<div>
The problem is not too big (~30 000 variables and about the same number of constraints), but it has a fairly large dense square block of about 10 000 x 10 000 variables.
</div>
<div>
Because of this block the thing takes huge amount of memory, but that's manageable for now - the problem is that I don't seem to be getting anywhere near a solution.
</div>
<div>
<br>
</div>
<div>
I have tried both the primal() and dual() algorithms with no success.
</div>
<div>
<div>
I know it is hard to tell anything without the exact problem being available, but since the .lp file is 700mb+ I do not have it uploaded anywhere at the moment (and it takes quite a lot time to load anyways).
</div>
<div>
What I have noticed so far while working with this problem is that the performance of the dual algorithm gets worse with the increase of the size of the dense block, however not always in the same way.
</div>
<div>
Certain types of input data may increase the block in terms of rows (number of constraints) and others - in terms of columns (number of variables). The increase in columns seems to be the more problematic part (for example, 10 000 x 500 is fairly trivial, while 10 000 x 10 000 is impossible so far; on the other hand, 50 000 x 500 is still solve-able in a very reasonable timeframe - faster than, for example, 10 000 x 2500).
</div>
</div>
<div>
<br>
</div>
<div>
I am wondering which one of the 2 options is more likely to be correct:
</div>
<div>
1. I am using the solver improperly and there is a way to actually have this passing much faster.
</div>
<div>
2. I should focus on ways to reformulate the problem (maybe find a way to break the dense block into something more sparse?) rather than trying to fine-tune the settings of the solver.
</div>
<div>
<br>
</div>
<div>
Any tips on the solver usage for such a problem will be greatly appreciated.
</div>
<div>
<br>
</div>
<div>
Thank you very much!
</div>
<br>
<fieldset class=""></fieldset>
<pre class="">_______________________________________________
Clp mailing list
<a class="" href="javascript: internSendMess('Clp@list.coin-or.org')">Clp@list.coin-or.org</a>
<a class="" href="https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=DwMDaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=7BSjjoINfZ7GRPk89AemxCmFYhZoN6OHgaoZ0XsjTEE&m=zrpdXtlkrE_yXRTYS1wE0EX9yGO510xUw8ZCuDibEf8&s=8nlVjOf4rjzXBTHdbdXNIUP3ppBuai4AxxHitbvJkno&e=" target="_blank">https://list.coin-or.org/mailman/listinfo/clp</a>
</pre>
</blockquote>
<p><br> </p>
</div></BODY></HTML>