Originally posted by: Feng Gao

Hi All,

I have a QP problem that has performance issue (take about one hour to solve). The default algorithm in CPLEX is barrier method.

I have the following quesitons:

1. Can barrier method be hot-started? If I provided a MPS BAS file, does barrier method accept it?

2. If barrier can not be hot-started? How about simplex type method? I tried primal and dual simplex method for QP. The performance

is a lot of worse than barried method. Does anyone observer the bad performance for simplex type method for QP.

3. During barrier method, I observe a lot of I/O activities. Specially, the cplex is writing some file:

"Creating directory ./cpxJBUh7a for Barrier out-of-core files
Writing 290MB factor matrix and 96MB update matrix
Out-of-core factorization with 128MB of working storage
54.76s for iteration (53.06s, 2002 Mflops for lin. solve)
Max number of central corrections is 3"

I have enough memory, why CPLEX access disk? If I increase more memory, can I solve the issue.

4. Here is the log file of barrier method. I understand the problem size is huge. Can CPLEX QP optimizer handle this kind of big problem within 15 mins.
QP Presolve eliminated 17581 rows and 33325 columns.
Reduced QP has 55912 rows, 623142 columns, and 9329086 nonzeros.
Compression time = 1.83 sec.
Compression reduced 136.72 MB A matrix to 32.44 MB
Looking for dense columns with more than 234 nonzeros.
Number of nonzeros in lower triangle of A*A' = 6369215
Elapsed ordering time = 20.47 sec.
Elapsed ordering time = 35.48 sec.
Elapsed ordering time = 50.49 sec.
Elapsed ordering time = 65.50 sec.
Elapsed ordering time = 80.51 sec.
Elapsed ordering time = 95.52 sec.
Elapsed ordering time = 110.53 sec.
Elapsed ordering time = 128.35 sec.
Elapsed ordering time = 149.43 sec.
Elapsed ordering time = 170.30 sec.
Elapsed ordering time = 193.89 sec.
Elapsed ordering time = 208.90 sec.
Elapsed ordering time = 223.91 sec.
Elapsed ordering time = 238.91 sec.
Elapsed ordering time = 253.92 sec.
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 268.35 sec.
Summary statistics for Cholesky factor:
Rows in Factor = 55912
Integer space required = 8912099
Total non-zeros in factor = 37999818
Total FP ops to factor = 105208025988
L has 28857 super-nodes.
Histogram of super-node widths:
SupWidth: 1 2 3 4 5 6 7 8 9
Number: 21534 3733 626 474 601 1090 219 285 25

SupWidth: 10 11 12 13 14 15 16 17 18
Number: 149 5 8 4 5 45 7 7 21

SupWidth: 20 21 24 26 28 30 39 68 110
Number: 4 6 1 1 1 1 1 1 1

SupWidth: 910 5067
Number: 1 1

Creating directory ./cpxJBUh7a for Barrier out-of-core files
Writing 290MB factor matrix and 96MB update matrix
Out-of-core factorization with 128MB of working storage
54.76s for iteration (53.06s, 2002 Mflops for lin. solve)
Max number of central corrections is 3
Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf
0 3.1835316e+12 -2.9595125e+12 3.95e+08 4.31e+08 1.65e+10
53.80s for iteration (53.00s, 2005 Mflops for lin. solve)
Iteration 1 did 3 central corrections 3260 vars
Refinement - orig 4.57e-01, refined 4.57e-01, target 7.90e+07, 0 iter
1 5.1583755e+11 -4.4367094e+11 1.52e+08 1.66e+08 6.37e+09
56.37s for iteration (52.96s, 2006 Mflops for lin. solve)
Iteration 2 did 3 central corrections 111780 vars
Refinement - orig 5.80e-07, refined 5.80e-07, target 3.04e+07, 0 iter
2 3.6383361e+10 -2.4194386e+10 3.28e+07 3.58e+07 1.37e+09
56.71s for iteration (53.34s, 1992 Mflops for lin. solve)
Iteration 3 did 3 central corrections 1438 vars
Refinement - orig 5.08e-07, refined 5.08e-07, target 6.56e+06, 0 iter
3 9.8986401e+09 -7.0809080e+09 1.42e+07 1.55e+07 5.93e+08
56.71s for iteration (53.25s, 1995 Mflops for lin. solve)
Iteration 4 did 0 central corrections 1 vars
Refinement - orig 1.64e-07, refined 1.64e-07, target 2.83e+06, 0 iter
...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: mangotree

Can someone help me on this issue? Thanks~~~
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

1. Can barrier method be hot-started? If I provided a MPS BAS file, does barrier method accept it?
No. First of all, barrier does not operate with a sequence of bases the way Simplex method does, so a BAS file would be meaningless to it. But even a hot start of trial solution values is not possible under the barrier algorithm.

2. How about simplex type method?
Simplex can benefit from an advanced starting basis. If you are solving a sequence of models, where the changes from one to the next model are not too large, the benefit can be quite large. (The Branch and Bound method for MIP depends greatly on this, for example.) In the past decade or so, Simplex has become stronger at solving models without a starting basis, so the value of a basis has declined. It's a matter of experimentation to know whether this would help in your case, to accept the pain of solving the first model in a sequence and then get the benefit for the ones that follow.

(2a.) The performance is a lot of worse than barried method.
On average, that's our experience as well for quadratic models, particularly if you don't need the crossover step to reach a simplex basis at the end. Of course, averages disguise a lot of unique individual behaviors, but apparently your model is in line with what we see, maybe even more strongly so.

3. During barrier method, I observe a lot of I/O activities.
First, it would help to be sure of which version of CPLEX you are using, and whether you are running with non-default parameter settings. It appears, for instance, that you have set the barrier display parameter to something non-default, judging by the kind of output you were able to show; so maybe some other parameters are also set.

The out-of-core factorization is designed to be a lot more efficient than letting an operating system's virtual memory perform the swapping, and normally the overhead of the feature is small. I am doubtful that avoiding it will give you the four-times faster speed you say you need. But it's certainly worth trying. You will notice in your output a reference to 128 Mbytes of working storage. That amount is controlled by the "WorkMem" parameter; it's wise to set this parameter to a value significantly lower than the amount of memory on your computer - if you have a gigabyte of RAM then setting WorkMem to 500 (megabytes) should be enough for this and somewhat larger models. In the Interactive Optimizer or OPL, use "set workmem 500", in a Callable Library application use CPX_PARAM_WORKMEM and in the variants of Concert use WorkMem.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: mangotree

Thanks for your answers to question 1 and 2!
For the 3rd question, our cplex version is 10.1. We are mainly using default options.
According to your suggestion, I increased WorkMem to a bigger value. I didn't see memory access issues.
That is good. But the overall QP perform is still relative slow. Maybe it is due to the size of the problem.
Can you please give some suggestions to improve?

I have another question on MIP and LP.
When we solve a MIP problem, the root relaxation problem takes about 100s. After we fixed all binary variables in the model to the values of that MIP solution and solve a LP problem for the rest of continuous variables. We observe that the LP usually take 5 mins, much longer than MIP root relaxation problem. However, it seems to me that MIP root relaxation problem is harder then the LP. Why LP is much slower? The default algorithm for LP is Dual Simplex. I guess root relaxation use a similiar method. Is that right?
For these 2 cases, we use most default options.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> mangotree wrote:

> When we solve a MIP problem, the root relaxation problem takes about 100s. After we fixed all binary variables in the model to the values of that MIP solution and solve a LP problem for the rest of continuous variables. We observe that the LP usually take 5 mins, much longer than MIP root relaxation problem. However, it seems to me that MIP root relaxation problem is harder then the LP. Why LP is much slower? The default algorithm for LP is Dual Simplex. I guess root relaxation use a similiar method. Is that right?
> For these 2 cases, we use most default options.

CPLEX will select the algorithm for the root relaxation based on some baked-in "intelligence", but I'm pretty sure it most often uses primal simplex at the root.

Are you saying that the solution to the root relaxation met all the integrality conditions? Or did you round the binary variables in the root relaxation solution before fixing them? If you rounded them, then the second LP is a different problem and could be considerably harder than the root relaxation.

If the root relaxation satisfies integrality restrictions and you fix the binary variables, you may still be modifying the LP a bit (changing 1-epsilon to 1 or epsilon to 0). If the LP structure is fundamentally stiff, a small modification like that could boost solution time by making it harder for CPLEX to meet feasibility tolerances.

/Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: mangotree

> Are you saying that the solution to the root relaxation met all the integrality conditions? Or did you round the binary variables in the root relaxation solution before fixing them? If you rounded them, then the second LP is a different problem and could be considerably harder than the root relaxation.

> If the root relaxation satisfies integrality restrictions and you fix the binary variables, you may still be modifying the LP a bit (changing 1-epsilon to 1 or epsilon to 0). If the LP structure is fundamentally stiff, a small modification like that could boost solution time by making it harder for CPLEX to meet feasibility tolerances.

Hi Paul,

I agree the 2nd LP may be different.

However, assuming 33% of total variables are binary. The number of variabls in the 2nd LP is reduced by 1/3 compared to MIP relaxation problem. The number constraints remain same.

Should CPLEX solve the 2nd LP (smaller one) quicker?

Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

We have a lot of sub-topics floating around here. I hope I don't get tangled up trying to address them.

Back to your QP that isn't solving fast enough in Barrier. If you have a multi-core computer, and a CPLEX license that supports parallel, then invoking multiple threads may help. You won't get linear speedups, but a 2X speedup on 4 cores is a reasonable expectation. Another thing that could help, based on the logfile, is to explicitly set the barrier ordering algorithm to '1', which might shave some time off of CPLEX's standard strategy of trying several orderings and see which is best.

On the MILP topic that you turned to, let me first suggest you try Barrier if you haven't already. I'm guessing that either LP degeneracy is playing a major role (causing similar problem instances to behave differently, more or less by luck), or numerical instability is present in the model, either because the underlying physical system being modeled is somewhat touchy or else numerical accuracy is being pushed beyond what can be solved. Examples of the latter are truncation of input data (0.333333 where 1/3 is the actual meaning, often coming from 32-bit single precision computation in whatever creates the data), or mixing of widely different scalings for example in a constraint like x - 1000000000 y <= 0. Barrier often can succeed when degeneracy is the culprit, while it is at least as vulnerable to numerical issues as Simplex is. Certainly, your supposition is reasonable that a smaller model (i.e. the same as the larger model except with some variables at fixed values) ought to solve faster, which is why I suspect some kind of pathological behavior is taking place.

To address a small sub-topic, under default settings, CPLEX will in most cases choose Dual Simplex rather than Primal Simplex during the various stages of solving the LP subproblems of a MILP, including the root solve.
#CPLEXOptimizers
#DecisionOptimization