How to model this constraint in a better way?

MIDCP
1

veca and vecb are know vectors. both of them have M element.
X and z are optimization variable.
M=2000 and N=4;
I am using Mosek.

I have modeled one of the constraints as

 for m=1:M
      for n=1:N
           z(m)>=X(veca(m),n)+X(vecb(m),n)-1;
      end
 end

But CVX keeps on running forever!

How can I fix this problem? A better modeling of the constraint? Ned your help

2

First of all the code looks strange because you overwrite the same z(m) with a new object N times in the loop. I find it unlikely that is what you meant.

Second, does CVX or the solver take the time? Do you have the log output? Do you have reproducible code?

3

The original problem I have is

for i=1:L
    for j=1:L
        for n=1:N
            if  W(i,j)>0 and i<j
                z(i,j)>=X(i,n)+X(j,n)-1;
            end
        end
    end
end

where W (L,L) is a known matrix and is symmetric. X(L,N) is optimization variable.

So, I tried to reduce the size of the problem by extracting all the pairs (i,j) for which W(i,j)>0. So, I removed the if condition.

Now, let’s says there are M such pairs.

veca contains the i’s

vecb contains the j’s

Now, the constraint becomes

for m=1:M
    for n=1:N
        z(m)>=X(veca(m),n)+ X(vecb(m),n)-1;
    end
end

Am I not doing i right?

4

That’s not what you wrote first, where you had = and not >=.

More to the point, have you looked where the long runtime is spent? Does the solver get called? Can you post the full log output?

5

Calling Mosek 9.1.9: 1696 variables, 1172 equality constraints

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 1172
Cones : 0
Scalar variables : 1696
Matrix variables : 0
Integer variables : 604

Optimizer started.
Mixed integer optimizer started.
Threads used: 12
Presolve started.
Presolve terminated. Time = 0.01
Presolved problem: 604 variables, 1172 constraints, 3516 non-zeros
Presolved problem: 0 general integer, 604 binary, 0 continuous
Clique table size: 80
BRANCHES RELAXS ACT_NDS DEPTH BEST_INT_OBJ BEST_RELAX_OBJ REL_GAP(%) TIME
0 0 1 0 5.3435304069e+02 NA NA 0.1
0 1 1 0 5.3435304069e+02 0.0000000000e+00 100.00 0.1
0 1 1 0 2.6639684719e+02 0.0000000000e+00 100.00 0.1
0 1 1 0 2.5699623154e+02 0.0000000000e+00 100.00 0.1
Cut generation started.
0 1 1 0 2.5699623154e+02 0.0000000000e+00 100.00 0.1
Cut generation terminated. Time = 0.00
0 9 1 0 2.2601093073e+02 0.0000000000e+00 100.00 0.2
7 20 1 0 2.2601093073e+02 0.0000000000e+00 100.00 0.2
22 35 1 0 1.7598504841e+02 0.0000000000e+00 100.00 0.2
29 42 1 0 1.5511410774e+02 0.0000000000e+00 100.00 0.2
36 46 1 0 1.5508072242e+02 0.0000000000e+00 100.00 0.2

and it goes on forever…

6

That’s very interesting, the relaxation won’t improve at all.

I suggest you first try the latest Mosek 10.0 and if that does not help then save the task file of the problem (instructions in 1 Technical Issues — MOSEK FAQ 10.0.44) and send to Mosek support email.

For a difficult MIP even if the solution starts to converge you may anyhow need to relax termination tolerances from 13.4 The Optimizer for Mixed-Integer Problems — MOSEK Optimization Toolbox for MATLAB 10.0.44 to finish before optimality. It is MIP so no free lunch.

I hope you are not setting cvx_precision best or anything like that. If you do, remove it.

7

How to use latest version of Mosekin CVX is addressed in How to speed up CVX for sparse, low-rank matrix recovery - #2 by Mark_L_Stone .

To set Mosek MIP absolute gap optimality tolerance to 0;05 and MIP relative gap optimality tolerance to 1% when Mosek is called from CVX

cvx_solver_settings('MSK_DPAR_MIO_TOL_ABS_GAP',0.05,'MSK_DPAR_MIO_TOL_REL_GAP',0.01)
Chnage the specified tolerance as desired.

8

Thanks. Is there anything I can do with the modeling? Remove the for loop, for example? If so, how can i do it?

9

But why? It will not help you with the solver time.

10

Have you tried any of the suggestions? I would be interested to know if it helps making progress on the relaxation. If not then we would really like see the task file at Mosek to check what is going on.