Originally posted by: uiowa_edu

Hi,

I'm encountering strange solution time results when solving a SOCP portfolio optimization (see below). Specifically, when I solve for 50 assets and 2500 randomly generated scenarios, the solution speed is much slower than for 50 assets / 5000 scenarios, which should not be the case as the latter is a much larger problem. For example, solution times averaged over twenty instances were 48.3 seconds for 50/2500, while 50/5000 solved in only 5.8 seconds. The problem is formulated as follows (I'll be happy to provide my code if anyone would be willing to look at it):

min: g + (1-a)^-1 * t
st: t >= (w_1^2 + ... +w_S)^2
w_s >= sum (a_is x_i) - eta, s = 1,...,S
sum( x_i ) = 1
expected return >= constant

x, w, t >= 0, g free
a_is = return for asset i in scenario s

Below is a sample pre-solution output for both cases. Notice the much larger "Total FP ops to factor" for the 50/2500 instance.

50 assets / 2500 scenarios
Tried aggregator 1 time.
Reduced QCP has 5052 rows, 2553 columns, and 132650 nonzeros.
Reduced QCP has 2 quadratic constraints.
Parallel mode: none, using 1 thread for barrier
Number of nonzeros in lower triangle of A*A' = 12627601
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 1.40 sec.
Summary statistics for Cholesky factor:
Rows in Factor = 5052
Integer space required = 7552
Total non-zeros in factor = 12633878
Total FP ops to factor = 42011105730

*50 assets / 5000 scenarios *
Tried aggregator 1 time.
Reduced QCP has 10052 rows, 5053 columns, and 265150 nonzeros.
Reduced QCP has 2 quadratic constraints.
Parallel mode: none, using 1 thread for barrier

***NOTE: Found 53 dense columns.

Number of nonzeros in lower triangle of A*A' = 5000
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec.
Summary statistics for Cholesky factor:
Rows in Factor = 10052
Integer space required = 10052
Total non-zeros in factor = 15052
Total FP ops to factor = 25052
I've also encountered this behavior in problems with different numbers of assets. Does anyone have any ideas why a smaller problem consistently requires MUCH more computation time? Is there anything I can do to fix this? I tries all qp solution methods, but non fixed the problem.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Christian Bliek

Hello,

From the logs this performance issue might be related to dense columns.

Our SOCP solver uses an interior point algorithm where properly identifying columns that are "dense" is key for good performance. This is a hard problem and we use a heuristic for doing it. It could be that our heuristic didn't properly identify dense columns in this case.

You can manually set the number of nonzeros above which a column is considered dense. This is done with "set bar colnz". To know what CPLEX uses as nonzero count do "set bar dis 2" and look at the diagnostic output. You probably want to set a higher nonzero count than what CPLEX does.

You can also get problem statistics about column nonzero counts using "dis prob hist c". However, be aware that for SOCP problems this doesn't tell the entire story as internally column unions over each cone are also considered.

In any case, we should try to improve our internal heuristic not to suffer the performance degradation you saw. So please send me your problem at "my last name" @fr.ibm.com.

Thanks,

Christian.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Christian Bliek

>You probably want to set a higher nonzero count than what CPLEX does.

Sorry, I meant to say, a lower nonzero count than what CPLEX does.
#CPLEXOptimizers
#DecisionOptimization