How can solve this Quadratic Assignment Interger Programming Problem by CVX

MIDCP
1

image
image1540×445 13.4 KB

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;
%oldID=readmatrix('30changeablesubsample.xlsx', 'Range', 'C2:C30')';
%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.
警告: A non-empty cvx problem already
exists in this scope.
It is being overwritten.

位置：cvxprob (第 28 行)
位置: cvx_begin (第 41 行)
位置: example (第 28 行)
错误使用 .*
Disciplined convex programming error:
Invalid quadratic form(s): not a
square.

出错 * (第 36 行)
z = feval( oper, x, y );

出错 example (第 46 行)
objectiveA = objectiveA + X(i,j) * (Y(i,j)-1);

2

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)

3

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.

4

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.

Before proceeding, please carefully read
Why isn't CVX accepting my model? READ THIS FIRST!

5

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.

6

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.

7

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

8

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

-entr(x)

9

Hello, in my thesis derivation, I used a similar form when dealing with binary variables. However, I noticed that you introduced the term X_i,j * (Y_i,j - 1) . Is this term intended to restrict X to be 0 or 1? If so, why is there no penalty coefficient in front of X_i,j * (Y_i,j - 1) ? Have you resolved this part of the problem? I would like to discuss the approach for handling this part. If possible, please contact me at 3217894389@qq.com.