Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only

QP optimizer performance issue

  • 1.  QP optimizer performance issue

    Posted Thu December 24, 2009 05:00 AM

    Originally posted by: mangotree


    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
    ...
    #DecisionOptimization
    #MathematicalProgramming-General