Answers to: Barrier optimizer in CPLEX: 1001 out of memoryhttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory<p>Can someone help me make heads and tails of this baropt run log? When I solve the same problem using dualopt, there is no problem and the problem solves withing a minute. However, the baropt run goes out of memory after the Nested Dissection. I want to try out Barrier algorithm as a similar problem is taking way too long using simplex, but gives the same out of memory error with baropt. Am I missing something here? Any settings that could help?</p>
<pre><code>CPLEX> baropt
Tried aggregator 1 time.
DUAL formed by presolve
Presolve has eliminated 15187 rows and 107403 columns...
LP Presolve eliminated 15187 rows and 107403 columns.
Reduced LP has 55731 rows, 257891 columns, and 9874640 nonzeros.
Presolve time = 32.66 sec.
Parallel mode: none, using 1 thread for barrier
Number of nonzeros in lower triangle of A*A' = 30472013
Elapsed ordering time = 22.27 sec.
Elapsed ordering time = 92.37 sec.
Elapsed ordering time = 108.59 sec.
Elapsed ordering time = 123.59 sec.
Elapsed ordering time = 138.60 sec.
Elapsed ordering time = 207.73 sec.
Elapsed ordering time = 225.54 sec.
Elapsed ordering time = 240.54 sec.
Elapsed ordering time = 255.55 sec.
Elapsed ordering time = 329.49 sec.
Elapsed ordering time = 349.14 sec.
Elapsed ordering time = 364.14 sec.
Elapsed ordering time = 379.16 sec.
Elapsed ordering time = 458.79 sec.
Elapsed ordering time = 475.91 sec.
Elapsed ordering time = 490.91 sec.
Elapsed ordering time = 505.92 sec.
Elapsed ordering time = 569.93 sec.
Elapsed ordering time = 586.81 sec.
Elapsed ordering time = 601.82 sec.
Elapsed ordering time = 616.82 sec.
Elapsed ordering time = 682.19 sec.
Elapsed ordering time = 699.81 sec.
Elapsed ordering time = 714.81 sec.
Elapsed ordering time = 729.81 sec.
Using Nested Dissection ordering
Total time for automatic ordering = 732.20 sec.
Summary statistics for Cholesky factor:
Rows in Factor = 55731
Integer space required = 2058825
Total non-zeros in factor = 746069701
Total FP ops to factor = 14248614220739
CPLEX Error 1001: Out of memory.
Barrier time = 782.27 sec.
</code></pre>enTue, 06 Dec 2011 23:59:48 -0500Answer by Anuraghttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/4170<p>Sorry for posting this so late. I tried some (~half) of the suggestions mentioned above, but couldn't get the optimizer to get rid of the error. However, while trying to solve the instances I did notice that both primal and dual simplex were having severe numerical stability issues. For example, variables that are bounded in the range [0,1] end up taking extremely large values, that keeps increasing if I let the solver run for longer. I did not run Bo's suggestions of running a degeneracy test though.</p>
<p>I ended up modeling my problem as a convex quadratic program towards the end of my project, for which I faced similar problems. However, I was able to code up a gradient descent algorithm that worked pretty well, so I never got around trying the other suggestions.</p>AnuragTue, 06 Dec 2011 23:59:48 -0500http://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/4170Answer by Ed Klotzhttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3111<blockquote>
<p>I have a few more suggestions, but it would be nice to know some more on the non zero pattern of the
A matrix.</p>
</blockquote>
<p>Interactive CPLEX offers some functionality to do this, both on the original and presolved models
(both the primal and dual). Use the commands 'display histogram c' and 'display histogram r' to
obtain nonzero counts for rows and columns. As stated above, dense rows in the primal translate
to dense columns in the dual. To see these histograms on the (unpresolved) dual model, read in
your model and write out a .dua file of the model; CPLEX will generate the dual model for you.
Read it back in and display the histograms. Similarly, to see them in the presolved model, write out a .pre file. With the presolve dual indicator turned on, the .pre file will contained the dual of the
presolved model.</p>
<p>Hopefully this information will help you determine whether the relatively dense Cholesky factor
involves a few dense rows on the primal (and hence dense columns in the dual) where changing
the barcolnz parameter will improve performance, or if, despite its large ratio of rows to
columns, solving the primal rather than the dual is more promising because the primal model
has few, if any, dense columns. If so, turn off CPLEX's presolve dual parameter.</p>
<pre><code> Ed
</code></pre>Ed KlotzTue, 28 Jun 2011 13:45:00 -0400http://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3111Answer by Bo Jensenhttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3086<p>I will throw in a new reply here, which is more aimed at playing with some odd possibilities.</p>
<p>First of all, it would be nice to know if the problem has a handful of dense rows or the density is widely spread on A ?</p>
<p>In the first case, you might actually be lucky and get around it, in the second case I think interior point to disc might be the best option.</p>
<p>Regarding degeneracy in the simplex method :</p>
<p>1) I assume you have tried both primal and dual on both primal and dual problem formulation, right ? If not try it. If you got dense rows, they become dense columns in the dual. In simplex, if such a column enters the basis, the algorithm slows down and will often make little progress.</p>
<p>2) Make a degeneracy test on all the options above. Perturb all bound and cost data, with a extremely large random factor (say 20% of largest value) i.e generate a new random number for each element. If this problem still takes very long time to solve, then using simplex is going to be hard.</p>
<p>3) If you got dense rows, you could do a heuristic to get a good starting point for the simplex algorithm, but it may end up in similar approach as the shifting algorithm. So you should also try to force using primal formulation and solve it with the shifting algorithm in CPLEX.</p>
<p>I have a few more suggestions, but it would be nice to know some more on the non zero pattern of the A matrix.</p>Bo JensenWed, 22 Jun 2011 12:49:45 -0400http://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3086Answer by Christian Bliekhttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3081<p>These are all good suggestions:</p>
<ul>
<li>memory emphasis on 1 thread will use our barrier out-of-core solver which writes intermediate results on disk, and hence should avoid running out of memory.</li>
<li>You can set the barcolnz parameter explicitly. To find out what value to set it to, you can display the problem histogram. Cplex does detect dense columns also in the dual formulation ;-)</li>
<li>It might be that presolve aggregation creates too dense rows in the primal (columns after taking the dual). So it may be worth limiting it or turning it off alltogether.</li>
</ul>
<p>Else send us you're model, and we'd be happy to take a look at it.</p>
<p>Christian.</p>
<p>FYI. We do routinely solve models with more factor non-zeros and FP ops than this one. But for this we use multithread machines with some decent amount of memory. </p>Christian BliekWed, 22 Jun 2011 10:55:01 -0400http://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3081Answer by Erlinghttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3080<p>Since, CPLEX formed the dual, then most likely it is dense rows that is the problems. Hence, CPLEX may overlook dense columns in the dual problem. Detecting the dense columns is not so easy unfortunately.</p>
<p>If you are will to make the problem public available then I can take a look at with MOSEK and see what comes up.</p>
<p>Erling (working for MOSEK).</p>ErlingWed, 22 Jun 2011 01:57:47 -0400http://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3080Answer by Paul Rubinhttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3073<p>I don't use barrier (or solve large problems), so the following are just guesses. You might try playing with CPLEX's BarColNz parameter, to see if special treatment of dense columns in the presolved model helps. The BarOrder parameter does what Bo suggested (alters ordering). You can turn MemoryEmphasis on -- it might slow the solution down, but it might avoid the out-of-memory error.</p>Paul RubinTue, 21 Jun 2011 17:56:52 -0400http://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3073Answer by Bo Jensenhttp://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3071<p>CPLEX log says :</p>
<blockquote>
<p>Total non-zeros in factor = 746069701</p>
</blockquote>
<p>which is quite a lot and the reason your machine run out of memory. Looking at the running time, I am sure the machine has been swapping for a long time.</p>
<p>Cholesky factor on <code>A*transpose(A)</code> is dependent on structure, if unlucky the structure of A makes <code>A*transpose(A)</code> very dense. As an example try to think of a matrix with sparsity pattern like a "arrow".</p>
<p>The best way to check the structure of A and gain better understanding is loading a smaller example into matlab (or octave) and use "spy" to play around with it.</p>
<p>You could play with different ordering methods, but I am not familiar with doing that in CPLEX.</p>
<p>Alternatively you could also try to switch off dual formulation, since I can see CPLEX presolve sets up the dual problem.</p>
<p>Contact CPLEX at their support forum and ask for help, they can properly come up with suggestions to reduce memory.</p>Bo JensenTue, 21 Jun 2011 15:59:14 -0400http://www.or-exchange.com/questions/3070/barrier-optimizer-in-cplex-1001-out-of-memory/3071