Wednesday, September 9, 2009

GAMS Cplex link issues with QCPs

I am working on a very large problem that involves electricity transmission. The losses over the transmission lines are quadratic functions modeled by piecewise linear functions. These functions cause the model to have many constraints. Using a quadratic formulation we can reduce the size of the problem significantly: we go from 1,248,614 rows to 784,934. This looks very promising. Unfortunately the GAMS Cplex link generates a Cplex model with many extra rows. We go from:

Reduced MIP has 943453 rows, 405564 columns, and 3247549 nonzeros.


to

Reduced MIQCP has 1035303 rows, 1047593 columns, and 3095839 nonzeros.


So all our effort to reduce the size of the model is wasted somehow.

The reason is a poor implementation of the quadratic terms. If we look at the small GAMS model:


variables z,x,y;
equation e;
y.lo=1;
e.. z =g= x*x+y;
model m /e/;
solve m minimizing z using qcp;

then the Cplex model that is generated contains extra rows:
\Problem name: gamsmodel

Minimize
obj: z + 0 x
Subject To
_e: z - y - linear_part_of_e  = 0
QCP_row_for_e: linear_part_of_e + [ - x ^2 ] >= 0
Bounds
      z Free
      x Free
      y >= 1
      linear_part_of_e Free
End

AMPL is doing much better. The model:
var x; var y >= 1; var z;
minimize obj:z;
e: z >= x*x+y;

generates the following Cplex model:
\Problem name: c3v1i0o1

Minimize
obj: 0 x1 + 0 x2 + x3
Subject To
c1: - x2 + x3 + [ - x1 ^2 ] >= 0
Bounds
      x1 Free
      x2 >= 1
      x3 Free
End

I reported this to the GAMS people, so hopefully this will be fixed quickly so I can really try my MIQCP formulation.