# How can solve this Quadratic Assignment Interger Programming Problem by CVX

I want to solve this Quadratic Assignment Interger Programming Problem by CVX. The mosek can not solve it directly if m=1008,n=29, (the size of X is large). so I solve the relaxing problem, 0<=X<=1, all entries of X in [0,1], each sum of row of X is 1. I penalty the X_i,j= 0 or 1 by X_ij(1-X_ij), To make the problem convex, I introduce an auxiliary variable Y, where X and Y are equal.

``````clc;
clear;

rng(123);

%parameter
n = 3;
m = 4;

A = randn(n);
A = A*A'+eye(n);
% Set a positive define matrix

w1=1;
%O= get_IDmatrix(n,oldID);

pho=100;
M=5;

%%

cvx_begin

% variable
variable X(n,m)
variable Y(n,m)

%objective

objectiveA = 0;
b=0;
for j = 1:m
objectiveA = objectiveA + w1 * quad_form(X(:, j), A);
end

for i=1:n
for j = 1:m

objectiveA = objectiveA + X(i,j) * (Y(i,j)-1);

end
end

a1=ones(n,1);
a2=ones(m,1);

minimize(objectiveA)

%constrit
subject to
0 <= X <= 1
X*a2 == a1
0 <= Y <= 1
Y*a2 == a1
X == Y
cvx_end
``````

However, it is worry.

exists in this scope.
It is being overwritten.

Disciplined convex programming error:
square.

z = feval( oper, x, y );

objectiveA = objectiveA + X(i,j) * (Y(i,j)-1);

Your attempted convexification doesn’t make sense.

However, `trace(X'*A*X)` can be reformulated as `square_pos(norm(sqrtm(A)*X,'fro'))`, which complies with CVX’s rules.

Given that it is the only term in the objective function, there is no need for the squaring (use of `square_pos`).

Similarly, the last constraint can be reformulated as
`norm(X-O,'fro') <= sqrt(2*M)`

Thank you. I have a question: how can I deal with the constraint of X_i,j=0 or 1. Why is there wrong for X_i,j*(Y_i,j-1) ? I think it is linear for X_i,j and Y_i,j, respectively.

it is not jointly linear, or jointly convex or concave. “Separately” (respectively) doesn’t count. When anything in CVX is required to be affine, or convex, or concave, that must hold jointly for all CVX (optimization) variables, not separately per variable

X = 0 or 1 can be handled by declaring `X` as binary:
`variable X(m,n) binary`
and then don’t include the relaxation `0 <= X <= 1`.

Of course, it is then a possibly difficult to solve MISOCP., which the QAP is. The relaxed version should be fast to solve, although its results might be garbage, other than providing a (possibly not very tight) lower bound on the optimal objective value.

Why isn't CVX accepting my model? READ THIS FIRST!

Thank you. Can I change my variable to x_i,j？ For example,
variable x_1,1
variable x_1,2
variable x_1,3 …
variable x_1,m
like this form.

Not with commas.

But anyhow, I don’t know why you want to do that. An n by m array (matrix) should be convenient, and also lends itself to vectorization of the CVX formulation, which at least reduces model formulation time, even though it might not help with solver time.

I suggest you carefully read the entirety of the CVX Users’ Guide.

If you are going to try to solve the QAP, start with small values of m and n.

I have a question, how does x*ln(x) be expressed in CVX?

As you will see at Reference guide — CVX Users' Guide

`-entr(x)`