Originally posted by: sguazt

Hi,

I'm using CPLEX 12.6.2  (C++ Concert API) to iteratively solve QP problems whose parameters (i.e., quadratic and linear terms) are formed online from external data. So I have no control on the values of those parameters.

Over 244 iterations performed on a test dataset , that DEFAULT algorithm (IloAuto) seems to have trouble 100% of the time (the solver exits with a status/substatus of NumBest), while the PRIMAL SIMPLEX algorithm (IloPrimal) has no problem.

So my question is, what is the most trustworthy algorithm to use for solving QP problems?

To get an idea of what I get with the default algorithm, I attach the SAV file of one of the problem I'm trying to solve.

And here below is the output I obtain with the DEFAULT and the PRIMAL SIMPLEX algorithms

- Output obtained with the DEFAULT algorithm:

Number of nonzeros in lower triangle of Q = 120
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (0.00 ticks)
Summary statistics for factor of Q:
  Rows in Factor            = 16
  Integer space required    = 16
  Total non-zeros in factor = 136
  Total FP ops to factor    = 1496
Tried aggregator 1 time.
QP Presolve eliminated 50 rows and 0 columns.
Reduced QP has 48 rows, 32 columns, and 336 nonzeros.
Reduced QP objective Q matrix has 16 nonzeros.
Presolve time = 0.00 sec. (0.06 ticks)
Parallel mode: using up to 4 threads for barrier.
Number of nonzeros in lower triangle of A*A' = 784
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (0.04 ticks)
Summary statistics for Cholesky factor:
  Threads                   = 4
  Rows in Factor            = 48
  Integer space required    = 128
  Total non-zeros in factor = 916
  Total FP ops to factor    = 21100
 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf
   0  -3.1615380e+19  -5.7144712e+09  3.19e+20  6.40e+19  6.16e+05
   1  -1.5807690e+17   5.0883852e+07  1.59e+18  3.20e+17  3.08e+03
   2  -7.9038450e+14  -1.4013906e+05  7.97e+15  1.60e+15  1.54e+01
   3  -3.9519225e+12  -1.7249390e+04  3.98e+13  8.00e+12  7.69e-02
   4  -1.9759612e+10  -1.6008787e+04  1.99e+11  4.00e+10  3.85e-04
   5  -9.8798063e+07  -1.6005332e+04  9.96e+08  2.00e+08  1.92e-06
   6  -4.9399009e+05  -1.6005286e+04  4.47e+06  1.00e+06  9.62e-09
   7  -2.4595897e+03  -1.6005254e+04  1.49e+05  5.00e+03  5.13e-11
   8   2.0440597e+05  -1.5998889e+04  1.89e+06  2.50e+01  4.46e-12
   9   1.0295250e+06  -1.4977560e+04  6.02e+07  1.25e-01  2.11e-12
  10   1.0057108e+07  -1.2024245e+04  7.44e+08  8.07e-04  2.34e-12
  11  -1.9248285e+07  -1.2007042e+04  4.26e+08  1.20e-04  1.75e-12
  12   1.5911892e+07  -1.2005440e+04  1.10e+09  1.43e-05  1.91e-12
  13   6.0513464e+06  -1.2005300e+04  8.21e+08  4.21e-08  2.57e-12
  14  -1.3975310e+07  -1.2005286e+04  1.04e+09  8.75e-17  2.61e-12
  15  -5.5212897e+07  -1.2005286e+04  6.33e+09  5.89e-17  2.69e-12
  *    1.0295250e+06  -1.4977560e+04  6.02e+07  1.25e-01  2.11e-12
Barrier time = 0.00 sec. (0.56 ticks)

Total time on 4 threads = 0.00 sec. (0.56 ticks)

- Output obtained with the PRIMAL SIMPLEX algorithm:
Number of nonzeros in lower triangle of Q = 120
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (0.00 ticks)
Summary statistics for factor of Q:
  Rows in Factor            = 16
  Integer space required    = 16
  Total non-zeros in factor = 136
  Total FP ops to factor    = 1496
Tried aggregator 1 time.
QP Presolve eliminated 50 rows and 0 columns.
Number of nonzeros in lower triangle of Q = 120
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (0.00 ticks)
Summary statistics for factor of Q:
  Rows in Factor            = 16
  Integer space required    = 16
  Total non-zeros in factor = 136
  Total FP ops to factor    = 1496
Reduced QP has 32 rows, 16 columns, and 184 nonzeros.
Reduced QP objective Q matrix has 256 nonzeros.
Presolve time = 0.00 sec. (0.07 ticks)

Using LP solver to compute a starting basis.

Iteration log . . .
Iteration:     1    Objective     =             1.226612

Thank you so much for the help.

Best,

-- Marco

Even if you say you cannot control the data, can you at least remove the constraints that are "<= 1e20"? Without these constraints CPLEX behavior looks much more reasonable here.

Originally posted by: sguazt

Indeed, it seems to work.

Those constraints were generated by statements like this:

--- [snip] ---

IloExpr lhs; // The left-hand side of a constraint

...

IloConstraint cons;

if (std::isfinite(input_data[i])) {

   cons = (lhs <= input_data[i]);

} else {

   cons = (lhs <= IloInfinity)

}

--- [/snip] ---

I thought it was a good idea to let CPLEX handle the infinity value by itself. But, as you pointed out, it's not.

So, I rearranged the construction of the constraint expressions so that non-finite values are ignored.

Thank you so much for the help.

Marco