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?

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.

asked 21 Jun '11, 15:46

Anurag's gravatar image

Anurag
7625
accept rate: 33%

edited 21 Jun '11, 17:57

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919

@Anurag: Do you have any results from the suggestions you received in this thread?

(06 Dec '11, 20:11) Samik R.
1

Samik, I have posted some of the things I ended up doing. I tried some of the suggestion, which didn't work. I ended up modeling my problem differently and solved it using gradient descent, but due to lack of time couldn't try out all the ideas posted here.

(07 Dec '11, 00:02) Anurag

CPLEX log says :

Total non-zeros in factor = 746069701

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.

Cholesky factor on A*transpose(A) is dependent on structure, if unlucky the structure of A makes A*transpose(A) very dense. As an example try to think of a matrix with sparsity pattern like a "arrow".

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.

You could play with different ordering methods, but I am not familiar with doing that in CPLEX.

Alternatively you could also try to switch off dual formulation, since I can see CPLEX presolve sets up the dual problem.

Contact CPLEX at their support forum and ask for help, they can properly come up with suggestions to reduce memory.

link

answered 21 Jun '11, 15:59

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

edited 21 Jun '11, 16:03

I tried the other two ordering methods provided. They were much faster than nested dissection. However, once the ordering was done, the same error appeared. It seems the trouble is elsewhere. Will try out some more stuff and post the results here. Thanks for your suggestions!

(22 Jun '11, 11:56) Anurag

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.

link

answered 21 Jun '11, 17:56

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Agree, dense columns (or rows) are properly the root cause. Initially the A matrix has 9874640 nonzeros, which is a lot compared to dimension. Such a dense problem may not be ideal for simplex either, since search direction also becomes dense and degenerated pivots are more likely.

(21 Jun '11, 18:05) Bo Jensen ♦

Bo, your assessment here might be right. Beyond a certain problem size, even simplex does not give the optimal after 10 hours. Paul, I'll try playing with BarColNz and MemoryEmphasis and let you know. Thanks!

(22 Jun '11, 11:59) Anurag

These are all good suggestions:

  • 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.
  • 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 ;-)
  • 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.

Else send us you're model, and we'd be happy to take a look at it.

Christian.

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.

link

answered 22 Jun '11, 10:55

Christian%20Bliek's gravatar image

Christian Bliek
411
accept rate: 0%

Christian, let me try out these suggestions.. I will post the results on this thread once I'm done. Unfortunately I don't think I can send the problem over. I'll let you know if I can. Thanks!

(22 Jun '11, 12:06) Anurag

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.

If you are will to make the problem public available then I can take a look at with MOSEK and see what comes up.

Erling (working for MOSEK).

link

answered 22 Jun '11, 01:57

Erling's gravatar image

Erling
4404
accept rate: 0%

edited 22 Jun '11, 02:01

Erling, thanks for your offer. I'm cannot make the problem public though (I'll try with my boss though). Let me try out some of the suggestions here first.

(22 Jun '11, 12:01) Anurag

I have a few more suggestions, but it would be nice to know some more on the non zero pattern of the A matrix.

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.

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.

                                                                                  Ed
link

answered 28 Jun '11, 13:45

Ed%20Klotz's gravatar image

Ed Klotz
23623
accept rate: 11%

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.

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.

link

answered 06 Dec '11, 23:59

Anurag's gravatar image

Anurag
7625
accept rate: 33%

1

Thanks for the status report. For the numerical stability issue, you could make cplex print the condition number, if large then numerical issues might be an issue. But I agree if basic variables increasingly take on huge numbers, that in itself is a sign of numerical instability. Please note you can have a basis matrix with "nice" numbers, which has a large condition number.

(07 Dec '11, 00:09) Bo Jensen ♦

Thanks, appreciate your comments.

(07 Dec '11, 00:27) Samik R.

I will throw in a new reply here, which is more aimed at playing with some odd possibilities.

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 ?

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.

Regarding degeneracy in the simplex method :

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.

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.

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.

I have a few more suggestions, but it would be nice to know some more on the non zero pattern of the A matrix.

link

answered 22 Jun '11, 12:49

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

edited 22 Jun '11, 12:56

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×190

Asked: 21 Jun '11, 15:46

Seen: 3,954 times

Last updated: 07 Dec '11, 00:27

OR-Exchange! Your site for questions, answers, and announcements about operations research.