Originally posted by: LeandroCC

Hello all,

I want to add a quadratic term to the objective function. Let Q be a matrix of coefficients, and x be my  binary variables:

I would need something like

//quadratic cost

for(int i = 1; i < n + 1; ++i)

for(int j = 1; j < m + 1; ++j)

for (int k=1; k < n+1; ++k)

for(int l = 1; l < m+1; ++l)

objexpr +=  Q[i][j][k][l] * x[i][j] * x[k][l];

I can then do a 

IloObjective obj(env, objexpr);

But when I do 

model.add(obj);

Then CPLEX stays for over one hour on the normalize() function (as seem from my debugger).

I tried simplifying things a bit by changing my loops to

//quadratic cost

for(int i = 1; i < n + 1; ++i)

for(int j = 1; j < m + 1; ++j)

for (int k=i+1; k < n+1; ++k)

for(int l = 1; l < m+1; ++l)

if ( l!=j )

objexpr += ( Q[i][j][k][l] + Q[k][l][i][j]) * x[i][j] * x[k][l];

but it didnt help at all. For what matters, the sizes of n and m range around 50.

Any help is much appreciated. Thanks!

Normalization on your expression is expected to be expensive since it has to check that in none of the 50⁴=6250000 terms a product x0*x1 occurs twice (and if the product occurs more than once then it has to merge the different terms into one).

You can disable normalization by env.setNormalizer(IloFalse) (see here) but then you need to make sure that all of your IloExpr instances are normalized.

Would one call to IloQuadProd produce the same result, and if so would it be any faster?

IloQuadProd will not help since it produces the same number of terms and normalization will again be slow.

Might be worth adding to the user request pile a request for a method that takes the Q matrix (in sparse form) and a vector x of variables and makes the quadratic portion of an expression x'Qx (or 1/2 x'Qx). If the method sets the quadratic terms to x'Qx, rather than adding x'Qx to the expression, and if the method requires that the x vector contain no duplicates (which CPLEX can check in linear time if you don't trust the users), I think the normalization step could be skipped.