How can I express these constraints in CVX?

MIDCP
1

I have a variable which I define as

    variable x(T,T) binary
    variable y(T,U) binary

\tau(u) is known which is an integer number (strictly positive)
t=1,2,\cdots, T and u=1,2,\cdots, U

There are many constraints in problem that I can write in CVX.

below are the constraints I am not able to express them in CVX.

  1. x_{t,t'}=x_{t',t}, \forall t\neq t'
  2. x_{t,t}+x_{t',t'}+x_{t,t'}\le 2, \forall t\neq t'
  3. y_{t,u}=x_{\tau(u),t}, \forall u, \forall t\neq \tau(u)

Any support is highly appreciated.

2

Constraint 1 is the same as declaring x to be symmetric (it also trivially holds for t = t' for any matrix, essentially constraining a scalar to equal itself).
variable x(T,T) binary symmetric

Constraints 2 and 3 can be handled by brute force with double for loops, making use of setdiff.

Here is constraint 2:

for t=1:T
  for tprime=setdiff(1:T,t)
    x(t,t)+x(tprime,tprime)+x(t,tprime) <= 2
  end
end

I believe this can at least be partially vectorized, eliminating the inner for loop, as follows (I advise you to check the correctness of this)

 for t=1:T
    x(t,t) + diag(x(setdiff(1:T,t),setdiff(1:T,t)))' + x(t,setdiff(1:T,t)) <= 2
 end

Constraint 3 should be a reasonably straightforward modification of the double for loop formulation for constraint 2; and I’ll leave it as an exercise for you. Bonus points for you if you can at least partially vectorize it.

3

Thanks a lot.
As you suggested, I do the following for constraint 3.
Let, tau_all=[tau_1,tau_2,tau_3, … , tau_U]

for u=1:U
    for t=setdiff(tau_all,tau_u)
        y(t,u)=x(tau_u,t)
    end
end

Would you please confirm if I am doing it correctly.

Thanks Again

4

You need tau_all(u) instead of tau_u. and == instead of =.

5

I think you could eliminate the inner for loop using
y(setdiff(tau_all,tau_all(u)),u) == x(tau_all(u),setdiff(tau_all,tau_all(u)))'

Eliminating the inner for loop saves a lot of CVX formulation (computer) time as the dimension increases. But the double for loop is just as “correct”. I don’t see how to eliminate the outer for loop for constraints 2 and 3, but if anyone knows how, they are welcome to post their formulation.

6

For constraint 1,

variable x(T,T) binary symmetric

is not doing the job as you say it also holds for t=t'.

But I have as you have already seen

x_{t,t'}=x_{t',t}, \forall t\neq t'

How can I do this in CVX?

7

You are requesting something nonsensical.

When t = t’, that (symmetry) constraint amounts to requiring x_{t,t} = x_{t,t}. How can that not hold? it is just saying that a variable must equal itself, which of course always holds.

So declaring the variable symmetric implements constraint 1 by any mathematically meaningful interpretation. it does not add any constraint beyond what is stated in 1. I.e., it implements constraint 1, and only constraint 1; no more, no less.

8

The first two are in this link How to deal with these constraints in CVX?.
The last one is the following:

t=1:T; 
a=1:T;
u=1:U;
t=t';
a=a';
u=u';
fir_cons=(repmat(a,1,U)==tau(repmat(u',T,1)));%au
sec_cons=(repmat(a,1,T)~=repmat(t',T,1));%at
sum_cons=repmat(fir_cons,[1,1,T]).*permute(repmat(sec_cons,[1,1,U]),[1 3 2]);%aut
permute(sum_cons,[3 2 1]).*(repmat( y , 1, 1, T ) - permute( repmat( x , 1, 1, U ), [ 2 3 1 ]))==0;

By the way, if conditions like ‘t~=tau(u)’ are removed and there just exists several layers of loops, I think most constraints(if not all) can be vectorized much easier.