Solving a QP - Cplex not applicable

[Bart de Peuter]

Dear all,

I am trying to solve a simple QP that involves only pairwise products of some vector of variables x that take values in {-1,1}.

Every pairwise product has a weight attached, and i want to optimize the sum of the weight*(pairwise products) using CPLEX.

The following implementation in YALMIP is used:

n=10;

%Define integer variables

x=intvar(n+1,1,'full');

%Define Matrix of pairwise products of x

y=x*x';

%Diagonal elements equal to one, to ensure the variables x in {-1,1}

constraints=[diag(y)==ones(n+1,1)];

%cMat is a symmetric matrix with a scalar for each pairwise product

objective = sum(sum(cMat.*y));

%Use Cplex

opts=sdpsettings;

opts.solver='cplex';

info = optimize(constraints,-objective,opts);

However, when running, i get the following warning:

'Warning: Solver not applicable (cplex)'

This is strange, since my constraints are linear equalities (involving pairwise products), and my objective is a linear function of these pairwise products.

Could anyone shed some light on this problem?

Attached you find a sample 'cMat' in .mat format .

Thanks a lot in advance!

All best,

Bart

[Johan Löfberg]

nothing attached

[Bart de Peuter]

Thanks for the quick response.

You are right indeed. Attached to this reply you find the mentioned matrix.

Thanks!

[Johan Löfberg]

and your constraints are quadratic equality constraints, which you cannot have with cplex

Why don't you write x = -1 + 2*binvar(n+1,1);

[Bart de Peuter]

Thanks Johan!

The constraints this way where derived from another model! 

[Bart de Peuter]

Dear Johan,

i may be misusing this topic, but do you know for a fact whether the approach to solve a QP is to linearize it to a MIP in cplex?

The reason for this question is that i rewrote an ILP to this QP to drastically decrease the number of variables and constraints, but , according to the CPLEX output, it is solving a problem with even more variables and constraints than my original problem.

Thanks for your time!

[Johan Löfberg]

For a convex QP as you have, I'm not sure but I would assume it is better to solve the QP. For a nonconvex QP, linearization is almost surely the best approach.

When I solve it (with x = -1+2*binvar) I see 11 variables printed, which is to be expected.

[Johan Löfberg]

Now I see what you mean (55 variables), looked at the wrong code

Yes, default appears to be linearization. There is a flag for that in the options somewhere

[Bartdp]

After turning the presolving phase off in CPLEX, the program is indeed solved as QIP (MIQP as CPLEX calls it). It is however reasonably slower to solve than it's ILP equivalent. 

Since the matrix cMat cannot be guaranteed to be PSD in my application, the QIP at hand is might be non-convex, which makes it hard to solve. Thanks for your effort Johan!