How can I make/transform this binary quadratic constraint CVX compatible?

MIDCP
1

I have a Binary Matrix \bf{A} of size N\times N, where N=100

I have an optimization variable matrix \bf U of size N\times M, where M=300

The constraint I have is

{\bf U}(:,m)^T{\bf A}{\bf U}(:,m)==0,m=1,2,\cdots,M

where, {\bf U}(:,m) is the $m$th column vector of \bf U, i.e., {\bf U}(:,m) is os size N\times 1

according to https://or.stackexchange.com/questions/924/how-can-i-linearize-or-convexify-this-binary-quadratic-optimization-problem

The constraints
{\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M

can be rewritten as
\sum_{i=1}^N \sum_{j=1}^N A(i,j) U(i,m)U(j,m)=0,m=1,2,\cdots,M.

Next, you can linearize each of the U(i,m)U(j,m) terms by introducing Z(i,j,m)=U(i,m)U(j,m) and adding the following constraints

Z(i,:,m) \leq U(i,m)\\Z(:,j,m) \leq U(j,m)\\Z(i,j,m) \geq U(i,m) + U(j,m) - 1

\sum_{i=1}^N \sum_{j=1}^N A(i,j) Z(i,j,m)=0,m=1,2,\cdots,M.

2

We’ll let folks handle it at https://or.stackexchange.com/questions/924/how-can-i-linearize-or-convexify-this-binary-quadratic-optimization-problem .

3

@Mark_L_Stone, Thanks. I have updated my problem statement according to the suggestions. I am a bit confused with the indexing. How can I now express this constraint in CVX?

4

Pretend that no variables have been declared in CVX, and this is just "regular"MATLAB. Handle the indexing accordingly. Now declare the CVX variables. The indexing will be the same. So this is really a MATLAB matter, not a CVX matter. You may wish to bone up on your knowledge of MATLAB syntax and indexing. Your problem just requires care.

7

I don;t believe your last for loop constraints are correct. Go back to the formuation you showed which you got at OR Stack Exchange,

Anyhow, formulating all these constraints in for loops is extremely time-consuming as you have seen. I suggest you start with a vary small version, just to demonstrate it runs and produces correct answers. You can of course also put in intermediate display output so that you see constraints as they are added and have some idea of progress…

To get this to run faster, it will have to be vectorized. I will leave it some someone more expert than me to suggest any improvements.

You could also try using YALMIP, which has binmodel to automate for you the conversion to MILP. https://yalmip.github.io/command/binmodel/ . Perhaps binmodel has a more efficient (faster) implementation than all your for loops. Plus, hopefully binmodel doesn’t make mistakes.

8

@Mark_L_Stone, thanks a lot. Surely I will look at the last loop formulation. Just from my curiosity, Gurobi works well with the problem of this size, right?

9

I have no idea how Gurobi will do on this. I don’t think your problem is particularly small. Actually, it appears you have 3 million binary variables for your original dimensions and 1.225 million for your N = 70, M = 250 version), which is quite large for a MILP. Solving MILPs is a crap shoot, and some smaller problems can be more difficult to solve than large problems. Worst case, the solar system will be extinct before your MILP is solved. But maybe Gurobi will solve this quickly once CVX completes its problem formulation.

Again, I advise you to start small, very small. See if you can get that to run correctly and fast enough. Perhaaps you need a completely different formulation which will be amenable to solution within a useful time frame.

10

@Mark_L_Stone. Thanks for your suggestions. I found an efficient formulation for my problem at https://or.stackexchange.com/questions/948/how-to-formulate-this-scheduling-problem-efficiently?noredirect=1#comment1459_948.

However, I am still defining the optimization variable in matrix form.

For the last constraint, I put all the adjacent pairs at Adjacecy_Pairs. Here is the CVX form I have for it. It is working, but its taking a very long time. How can I make it faster?

cvx_begin 


variable Z(N,M) binary
variable v

s=sum(Q.*Z,2);

maximize v

subject to

    s>=t.*d;
    sum(Z,1)<=11;
    
    for m=1:M
    for nap=1:N_AP
        abeams=Adjacent_Pairs(nap,:);
        Z(abeams(1),m)+Z(abeams(2),m)<=1;
    end
    end



cvx_end
11

Can you eliminate the for m=1:M loop and change
Z(abeams(1),m)+Z(abeams(2),m)<=1;
to
Z(abeams(1),:)+Z(abeams(2),:)<=1;

12

yes, it faster now! Thanks a lot.