Thursday, August 30, 2012

Cplex QP problems

For a reasonable sized continuous QP problem, the default Cplex settings indicate problems:

Reading data...
Starting Cplex...
Tried aggregator 1 time.
QP Presolve eliminated 51 rows and 60 columns.
Aggregator did 600 substitutions.
Reduced QP has 1404 rows, 25401 columns, and 58593 nonzeros.
Reduced QP objective Q matrix has 24979 nonzeros.
Presolve time =    0.03 sec.
Parallel mode: none, using 1 thread for barrier
Number of nonzeros in lower triangle of A*A' = 23873
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec.
Summary statistics for Cholesky factor:
  Rows in Factor            = 1404
  Integer space required    = 12305
  Total non-zeros in factor = 37816
  Total FP ops to factor    = 1398232
Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf         
   0  1.1269359e+016 -1.1269360e+016 1.03e+006 0.00e+000 6.83e+014
   1  1.3889591e+015 -1.3889592e+015 3.62e+005 0.00e+000 2.40e+014
   2  5.4393422e+013 -5.4393451e+013 7.16e+004 0.00e+000 4.75e+013
   3  4.9247681e+011 -4.9248040e+011 6.82e+003 0.00e+000 4.51e+012
   4  2.8122639e+009 -2.8128116e+009 5.15e+002 0.00e+000 3.41e+011
   5  1.2862048e+008 -1.2878713e+008 1.10e+002 0.00e+000 7.29e+010
   6  1.6614552e+006 -1.6932044e+006 1.25e+001 0.00e+000 8.26e+009
   7  3.0507032e+003 -9.1387053e+003 1.16e-001 0.00e+000 7.70e+007
   8  8.8731205e+002 -2.6509477e+003 3.31e-002 0.00e+000 2.19e+007
   9  3.2742736e+002 -5.8146949e+002 8.03e-003 0.00e+000 5.32e+006
  10  2.4615010e+002 -2.3471413e+002 4.40e-003 0.00e+000 2.92e+006
  11  2.0803982e+002 -3.1756372e+001 2.26e-003 0.00e+000 1.50e+006
  12  1.8984146e+002  9.9701542e+001 8.66e-004 0.00e+000 5.74e+005
  13  1.8441405e+002  1.5886308e+002 2.46e-004 0.00e+000 1.63e+005
  14  1.8341125e+002  1.7590746e+002 7.24e-005 0.00e+000 4.80e+004
  15  1.8320505e+002  1.8209849e+002 1.04e-005 0.00e+000 6.88e+003
  16  1.8318478e+002  1.8309471e+002 7.96e-007 0.00e+000 5.27e+002
  17  1.8318341e+002  1.8318113e+002 1.57e-008 0.00e+000 1.04e+001
  18  1.8318336e+002  1.8318333e+002 1.14e-010 0.00e+000 7.37e-002
  19  1.8318506e+002  1.8317840e+002 3.79e-011 0.00e+000 3.91e-004
  20  1.8318506e+002  1.8317840e+002 3.12e-007 0.00e+000 3.44e+004
  *   1.8318506e+002  1.8317840e+002 3.79e-011 0.00e+000 3.91e-004

Total time on 1 threads =    0.19 sec.
QP status(6): non-optimal

Solution available but not proven optimal due to numerical difficulties.

This is a matrix balancing problem, where we try to repair economic data matrices after dropping small values, while maintaining some important economic identities.

First thing I tried was to use primal and dual simplex methods, but these turned out not very attractive alternatives (primal simplex took a long time, and dual simplex was infeasible after unscaling). The best option turned out to be using the opfion  numericalemphasis. Now it solves fine. Of course I believe that I should not have to do this: Cplex itself should understand better than me that it is in trouble and should try to recover from this in a more intelligent way than I can.