Return solution infeasible for mixed integer programming problem with SDP constraints using BNB

[Yuting Chen]

Hi everyone,

I am trying to use the bnb solver to solve an integer linear programming problem with SDP constraints. the solver returns a solution with no error code, however, the actual solution tends out to be infeasible (the Q matrix tends out to be indefinite)

My problem is of following structure:

n = 20;

x = binvar(n,1); % x is the binary variable vector

Q = [Q2(x)] - eps*eye(2*n);
% Q2(x) is some matrix related to x that I would like it to be positive definite
% eps is a small positive number ranging from say 0.0001~0.001


F = set( Q > 0 ); % set Q to be p.d.
F = F + set(sum(x)<=k); % set the number of non-zero entries of x to be smaller than some integer k

ops = sdpsettings();
ops.verbose = 1;
ops.bnb.maxiter = 1000;
ops.savesolveroutput = 1;
 
info = solvesdp(F, -f'*x,ops); % my objective is to max_x f'x s.t. the positive definite constraint

This is the output from calling the solver:

* Starting YALMIP integer branch & bound.

* Lower solver   : PENSDP-TOMLAB

* Upper solver   : rounder

* Max iterations : 1000

 Node       Upper       Gap(%)      Lower    Open

    1 :   -2.436E+00    59.64     -9.639E+00   2  Successfully solved 

    2 :   -2.436E+00    59.64     -9.639E+00   3  Successfully solved 

    3 :   -2.436E+00    59.64     -9.639E+00   4  Successfully solved 

    4 :   -2.436E+00    59.64     -9.639E+00   5  Successfully solved 

    5 :   -2.436E+00    59.64     -9.637E+00   6  Successfully solved 

    6 :   -2.436E+00    59.64     -9.637E+00   7  Successfully solved 

    7 :   -2.436E+00    59.61     -9.630E+00   8  Successfully solved 

    8 :   -2.436E+00    59.61     -9.630E+00   9  Successfully solved 

    9 :   -2.436E+00    59.61     -9.629E+00  10  Successfully solved 

   10 :   -2.436E+00    59.61     -9.629E+00  11  Successfully solved 

   11 :   -2.436E+00    59.58     -9.621E+00  12  Successfully solved 

   12 :   -2.436E+00    59.58     -9.621E+00  13  Successfully solved 

   13 :   -2.436E+00    59.58     -9.621E+00  14  Successfully solved 

   14 :   -2.436E+00    59.58     -9.621E+00  15  Successfully solved 

   15 :   -2.436E+00    59.55     -9.612E+00  16  Successfully solved 

   16 :   -3.666E+00    44.78     -9.612E+00  17  Successfully solved 

   17 :   -3.666E+00    44.58     -9.564E+00  18  Successfully solved 

   18 :   -3.666E+00    44.58     -9.564E+00  19  Successfully solved 

   19 :   -5.447E+00    27.40     -9.559E+00  20  Successfully solved 

   20 :   -5.447E+00    27.40     -9.559E+00  21  Successfully solved 

   21 :   -5.447E+00    26.59     -9.394E+00  22  Successfully solved 

   22 :   -5.447E+00    26.59     -9.394E+00  23  Successfully solved 

   23 :   -5.447E+00    26.47     -9.369E+00  24  Successfully solved 

   24 :   -5.447E+00    26.47     -9.369E+00  25  Successfully solved 

   25 :   -5.447E+00    26.40     -9.356E+00  26  Successfully solved 

   26 :   -5.447E+00    26.40     -9.356E+00  27  Successfully solved 

   27 :   -5.447E+00    26.36     -9.347E+00  28  Successfully solved 

   28 :   -5.447E+00    26.36     -9.347E+00  29  Successfully solved 

   29 :   -5.447E+00    26.35     -9.346E+00  30  Successfully solved 

   30 :   -5.447E+00    26.35     -9.346E+00  31  Successfully solved 

   31 :   -5.447E+00    26.33     -9.342E+00  32  Successfully solved 

   32 :   -5.447E+00    26.33     -9.342E+00  33  Successfully solved 

   33 :   -5.447E+00    26.33     -9.341E+00  34  Successfully solved 

   34 :   -5.447E+00    26.33     -9.341E+00  35  Successfully solved 

   35 :   -5.447E+00    26.30     -9.336E+00  36  Successfully solved 

   36 :   -5.447E+00    26.30     -9.336E+00  37  Successfully solved 

   37 :   -5.447E+00    26.29     -9.334E+00  38  Successfully solved 

   38 :   -5.447E+00    26.29     -9.334E+00  39  Successfully solved 

   39 :   -5.447E+00    26.29     -9.333E+00  40  Successfully solved 

   40 :   -5.447E+00    26.29     -9.333E+00  41  Successfully solved 

   41 :   -5.447E+00    26.28     -9.330E+00  42  Successfully solved 

   42 :   -5.447E+00    26.28     -9.330E+00  43  Successfully solved 

   43 :   -5.447E+00    26.26     -9.326E+00  44  Successfully solved 

   44 :   -5.447E+00    26.26     -9.326E+00  45  Successfully solved 

   45 :   -5.447E+00    26.26     -9.326E+00  46  Successfully solved 

   46 :   -5.447E+00    26.26     -9.326E+00  47  Successfully solved 

   47 :   -5.447E+00    26.22     -9.319E+00  48  Successfully solved 

   48 :   -5.447E+00    27.69     -9.620E+00  49  Maximum iterations or time limit exceeded 

   49 :   -5.447E+00    27.69     -9.620E+00  50  Maximum iterations or time limit exceeded 

   50 :   -5.447E+00    26.97     -9.470E+00  51  Maximum iterations or time limit exceeded 

   51 :   -9.651E+00     0.00     -9.651E+00   0  Maximum iterations or time limit exceeded 

+  51 Finishing.  Cost: -9.6512

The problem is supposed to be successfully solved since the gap between upper and lower bound is shown as 0% and the output of the solver is shown as correct.

info.problem = 0

I am concerned about the last notification "Maximum iterations or time limit exceeded", any idea why this is shown here even when the gap is zero? Sometimes there is not even any abnormal notification shown (yet the solution x is infeasible as before):

* Starting YALMIP integer branch & bound.

* Lower solver   : PENSDP-TOMLAB

* Upper solver   : rounder

* Max iterations : 1000

 Node       Upper       Gap(%)      Lower    Open

    1 :   -1.404E+00    52.58     -4.518E+00   2  Successfully solved 

    2 :   -1.404E+00    52.58     -4.518E+00   3  Successfully solved 

    3 :   -1.404E+00    52.58     -4.518E+00   4  Successfully solved 

    4 :   -1.404E+00    52.58     -4.518E+00   5  Successfully solved 

    5 :   -4.518E+00     0.00     -4.518E+00   2  Successfully solved 

+   5 Finishing.  Cost: -4.5177

The output x is supposed to be feasible and the corresponding Q should be p.d or at least p.s.d, however, the minimum eigenvector is a small negative number, usually equal to - eps (which indicates that the matrix Q2(x) has 0 eigenvalues). I tried to increase or decrease eps but the same problem stays.

The output x is infeasible but due to some reason the solver didn't report it... and this is happening for a small scale problem where x is a 20*1 vector.

I have the following questions:

1) Anyone has any idea why this is happening? (return an infeasible solution without any notification)

2) Is there anything wrong with my BNB setting or anything wrong with BNB itself?

3) Can anyone point a direction of solving an mixed integer programming problem with SDP constraints? (what other solvers to use)

Thanks in advance !

Yuting

[Johan Löfberg]

1. The message Maximum iterations or time limit exceeded is the message the lower bound solver (pensdp) returned when solving the relaxation. This message means you should be careful about drawing too strong conclusions about the lower bound, since the lower bound computation has had problems

2. When you say the solution is infeasible, how infeasible? Violating positive semidefiniteness with 10^-7 or less is to be expected.

3. Try another local solver. Since pensdp apparantly struggles in some nodes, you should try something else. Mosek is a good bet in a MISDP situation, since the overhead is very low, hence it is fast when solving many small problems

4. SET is obsolete
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Set

5. Strict inequalities is not supported. You should see warnings about this.
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Blog.Prepare-your-code

I cannot say anything more unless you supply the code for Q2

[Yuting Chen]

Thanks a lot Johan,

1. The message Maximum iterations or time limit exceeded is from the lower bound solver not the upper bound solver bnb? If so, why the upper bound estimation jumps from -5.44 in #50 to -9.65 in #51 and thus produces a 0% gap? (or from -1.40 to -4.52 in the second example). I thought the message was from bnb since it is jumping...

2. when I say infeasible, the Q matrix (which is set to be p.d or p.s.d) has a smallest eigenvalue of about -1e-4 or so (it depends on the value of eps, since my constraint is Q = Q2 - eps I > 0) so basically the Q2 matrix has a zero eigenvalue and Q matrix has a - eps eigenvalue

3. I'll try and test that local solver. Should I use it as upper solver or lower solver?

4 & 5 thanks for the heads-up, I'll update them. 

Yuting

[Johan Löfberg]

1. The right-most message is information about the lower bound problem.

2. If you use Q2 - eps I > 0 you would expect Q2 to have a positive eigenvalue eps+-10^-7 or so, so the -eps eigenvalue you talk about is strange. It looks as if the solution returned from pensdp in the last iterate is integer, but violates the SDP constraints, and YALMIP fails to check psd conditions. Most easily debugged if you post code which I can run (or send it to me joh...@isy.liu.se)

3. The SDP solver is the lower solver. The upper solver is basically just heuristics to round the solution. No real option there to change yet

[Yuting Chen]

Thanks again Johan,

1. I am just curious why the upper bound would jump that much in one iteration...

2. I'll try to make up a minimum working example 

Thanks,

Yuting

[Yuting Chen]

Thanks Johan, I've sent you a sample code. I am working on alternative solvers in the meantime.

[Johan Löfberg]

The lower and upper bound can jump unpredictably, typical mixed-integer behaviour. Note however, that the lower bound decreases on the last four b&b iterations in the first example. This is not possible in theory, and is a consequence of the wrong solution returned by pensdp in these nodes

[Yuting Chen]

Hi Johan,

I understand how upper bound can jump in the process, but the jump of the last iteration is from 20% to 0%-meaning global optimum is achieved, while the output is in fact infeasible.... That is what I found hard to understand...

I also tried Mosek as lower solver as you suggested, however the same problem happens: there's no error notification what so ever, while the output is still infeasible

* Starting YALMIP integer branch & bound.

* Lower solver   : MOSEK-SDP

* Upper solver   : rounder

* Max iterations : 1000

 Node       Upper       Gap(%)      Lower    Open

    1 :    0.000E+00    99.99     -1.225E+01   2  Successfully solved 

    2 :    0.000E+00    99.99     -1.225E+01   3  Successfully solved 

    3 :   -7.890E-01    87.89     -1.225E+01   4  Successfully solved 

    4 :   -7.890E-01    87.89     -1.225E+01   5  Successfully solved 

    5 :   -7.890E-01    87.89     -1.225E+01   6  Successfully solved 

    6 :   -7.890E-01    87.89     -1.225E+01   7  Successfully solved 

    7 :   -7.890E-01    87.89     -1.225E+01   8  Successfully solved 

    8 :   -7.890E-01    87.89     -1.225E+01   9  Successfully solved 

    9 :   -7.890E-01    87.89     -1.225E+01  10  Successfully solved 

   10 :   -7.890E-01    87.89     -1.225E+01  11  Successfully solved 

   11 :   -7.890E-01    87.89     -1.225E+01  12  Successfully solved 

   12 :   -7.890E-01    87.89     -1.225E+01  13  Successfully solved 

   13 :   -7.890E-01    87.89     -1.225E+01  14  Successfully solved 

   14 :   -7.890E-01    87.89     -1.225E+01  15  Successfully solved 

   15 :   -7.890E-01    87.89     -1.225E+01  16  Successfully solved 

   16 :   -7.890E-01    87.89     -1.225E+01  17  Successfully solved 

   17 :   -7.890E-01    87.89     -1.225E+01  18  Successfully solved 

   18 :   -7.890E-01    87.89     -1.225E+01  19  Successfully solved 

   19 :   -7.890E-01    87.89     -1.225E+01  20  Successfully solved 

   20 :   -7.890E-01    87.89     -1.225E+01  21  Successfully solved 

   21 :   -7.890E-01    87.89     -1.225E+01  22  Successfully solved 

   22 :   -7.890E-01    87.89     -1.225E+01  23  Successfully solved 

   23 :   -7.890E-01    87.89     -1.225E+01  24  Successfully solved 

   24 :   -7.890E-01    87.89     -1.225E+01  25  Successfully solved 

   25 :   -7.890E-01    87.89     -1.225E+01  26  Successfully solved 

   26 :   -1.225E+01     0.00     -1.225E+01   1  Successfully solved 

+  26 Finishing.  Cost: -12.2467

% info.problem
ans =

     0

% smallest eigenvalue

ans =

  -1.0000e-05

In the above example (I've send you a sample code containing the same problem), the lower bound is not changing over the iterations, yet somehow the upper bound jumps by ~80% in the last iteration and altogether produces an infeasible solution...

1) I am wondering if this is caused by some mis-communication between the lower solver and bnb. If so, any way to correct this?

2) I am also wondering whether there exists another branch-and-bound solver to solve my problem (integer programming with SDP constraints), I coarsely browsed Mosek, Tomlab and so on, they all have models for mixed integer programming with linear/quadratic constraints, and SDP solvers, but I had no luck finding a model for solving integer programming with SDP constraints... Could you please point me some possible directions?

Again, thanks a lot for your replies.

Yuting

[Johan Löfberg]

The progress of the gap is simply not predictable. You can have problems where the models chugs along for thounds of iterations with an infinite gap (i.e., no feasible solution found), and then bam, a solution is feasible and matches the lower bound, and the gap is closed completely. It is just the nature of integer programming.

This new behavior is a peculiar combination of tolerances. YALMIP considers a solution to be integer feasible when distance is less than ops.bnb.inttol to integrality. In this final node, this test is passed. However, when the solution actually is rounded (which YALMIP does for you if you have ops.bnb.round set to 1), the LMI constraint is significantly violated. Your only option then is to decrease the integrality tolerance below you tolerance for the LMI condition.

BTW, I discovered a small issue in Mosek earlier this morning, showing up when solving your problem for some choice of parameters. They have fixed this in their beta 7, but you should be aware (you will see the lower bound go to -infinity all of a sudden, which of course makes no sense, as the lower bound should be monotonically non-decreasing)

[Johan Löfberg]

No, I am not aware of any other public MISDP solver. You are stuck with YALMIP muhahaha :-). There is an alternative MISDP solver in YALMIP called cutsdp. It solves MILP relaxations of the MISDP and then add cuts based on SDP infeasibility. Does not perform well here either.

MISDP takes much more manual labour than MILPs etc. You have to come up with clever cuts etc, things that MILP solvers do for you automatically.

[Yuting Chen]

Yeah I found the same problem with Mosek too, the lower bound just jumps to -inf... 

Thanks for your explanation and I guess now I kind of understand why the solver returns infeasible solution... I'll try decrease the integrality tolerance and see what happens

[Yuting Chen]

Ha, you made me laugh :-)

If I understand correctly, are you suggesting that the cutsdp solver requires more manual labour than bnb?

BTW, it is really so nice of you during so many years to still help out on us newbies. Salute!

 

[Johan Löfberg]

No, I mean that to solve MISDPs in general, you have to work more with the model before sending it to a crappy solver such as bnb or cutsdp. A MILP solver such as cplex or mosek etc has a large number of tricks up their sleeve, and these are not available in the simple solvers bnb or cutsdp. These tricks, you have to come up with manually, and distill as much as information from the model as possible.

Example. You have a constraints of the type [diag(A) diag(x);diag(x) C] >= 0. What can you infer from this? Well, it follows that diag(A) >= (x*x').*inv(C). Can you use this to derive interesting information on x? I tried, did not find anything. Looking at the diagonals for instance, you get constraints such as 6-eps+x(2)+x(8)>=5.97*x(1) (using the fact that x(1)^2 = x(1)). This does not cut away anything interesting since any choice of x(1), x(2) and x(8) is feasible

[Yuting Chen]

I tried a smaller integrality tolerance 1e-7 (and smaller ones), however the same problem stays and the minimum eigenvalue is still as negative as - eps ( - 1e-4 or so)... I tried increase or decrease eps and nothing seems to push the solver to actually stop at a real feasible solution...

I guess the rounding in the last step just messes things up ... :-( would it be possible to make sure the solver checks for LMI constraint again after the rounding step before stop the iteration process?

[Johan Löfberg]

What is displayed when you do that? Don't confuse the early termination due to integer tolerance with the core bug in Mosek which causes the lower bound to be -inf which confuses YALMIP to terminate early. Checking post-rounding would be possible, but I don't think it is the logic way to do it, since it would mix the logic of integer feasibility and relaxed feasibility. If you want to avoid this, you must use a tighter tolerance on integrality.

It works as expected here when I use, e.g., 1e-6 (i.e., runs forever...) (using the fixed version of Mosek 7)

ops = sdpsettings('bnb.inttol',1e-6);
ops.bnb.inttol = 1e-6;

[Yuting Chen]

Hi, the display I got from Mosek is as follows (my eps = 1e-4, ops setting the same as yours), my Mosek version is 7.0.0.63, does this version still has the problem you mentioned? 

* Starting YALMIP integer branch & bound.

* Lower solver   : MOSEK-SDP

* Upper solver   : rounder

* Max iterations : 1000

 Node       Upper       Gap(%)      Lower    Open

    1 :    0.000E+00    99.99     -1.224E+01   2  Successfully solved 

    2 :    0.000E+00    99.99     -1.224E+01   3  Successfully solved 

    3 :   -7.890E-01    87.89     -1.224E+01   4  Successfully solved 

    4 :   -7.890E-01    87.89     -1.224E+01   5  Successfully solved 

    5 :   -7.890E-01    87.89     -1.224E+01   6  Successfully solved 

    6 :   -7.890E-01    87.89     -1.224E+01   7  Successfully solved 

    7 :   -7.890E-01    87.89     -1.224E+01   8  Successfully solved 

    8 :   -7.890E-01    87.89     -1.224E+01   9  Successfully solved 

    9 :   -7.890E-01    87.88     -1.224E+01  10  Successfully solved 

   10 :   -7.890E-01    87.88     -1.224E+01  11  Successfully solved 

   11 :   -7.890E-01    87.88     -1.224E+01  12  Successfully solved 

   12 :   -7.890E-01    87.88     -1.224E+01  13  Successfully solved 

   13 :   -7.890E-01    87.88     -1.224E+01  14  Successfully solved 

   14 :   -7.890E-01    87.88     -1.224E+01  15  Successfully solved 

   15 :   -7.890E-01    87.88     -1.224E+01  16  Successfully solved 

   16 :   -7.890E-01    87.88     -1.224E+01  17  Successfully solved 

   17 :   -7.890E-01    87.88     -1.224E+01  18  Successfully solved 

   18 :   -7.890E-01    87.88     -1.224E+01  19  Successfully solved 

   19 :   -7.890E-01    87.88     -1.224E+01  20  Successfully solved 

   20 :   -7.890E-01    87.88     -1.224E+01  21  Successfully solved 

   21 :   -7.890E-01    87.88     -1.224E+01  22  Successfully solved 

   22 :   -7.890E-01    87.88     -1.224E+01  23  Successfully solved 

   23 :   -7.890E-01    87.88     -1.224E+01  24  Successfully solved 

   24 :   -7.890E-01    87.88     -1.224E+01  25  Successfully solved 

   25 :   -7.890E-01    87.88     -1.224E+01  26  Successfully solved 

   26 :   -7.890E-01    87.88     -1.224E+01  27  Successfully solved 

   27 :   -7.890E-01    87.88     -1.224E+01  28  Successfully solved 

   28 :   -2.026E+00    71.59     -1.224E+01  29  Successfully solved 

   29 :   -2.026E+00    71.59     -1.224E+01  30  Successfully solved 

   30 :   -4.341E+00    47.65     -1.224E+01  31  Successfully solved 

   31 :   -4.341E+00    47.63     -1.224E+01  32  Successfully solved 

   32 :   -4.341E+00    47.63     -1.224E+01  33  Successfully solved 

   33 :   -4.341E+00    47.62     -1.223E+01  34  Successfully solved 

   34 :   -4.341E+00    47.62     -1.223E+01  35  Successfully solved 

   35 :   -4.341E+00    47.62     -1.223E+01  36  Successfully solved 

   36 :   -4.341E+00    47.62     -1.223E+01  37  Successfully solved 

   37 :   -4.341E+00    47.61     -1.223E+01  38  Successfully solved 

   38 :   -4.341E+00    47.61     -1.223E+01  39  Successfully solved 

   39 :   -4.341E+00    47.50     -1.220E+01  40  Successfully solved 

   40 :   -4.341E+00    47.50     -1.220E+01  41  Successfully solved 

   41 :   -4.341E+00    47.35     -1.215E+01  42  Successfully solved 

   42 :   -4.341E+00    47.35     -1.215E+01  41  Infeasible problem 

   43 :   -4.341E+00    47.22     -1.211E+01  40  Infeasible problem 

   44 :   -4.341E+00    47.22     -1.211E+01  41  Successfully solved 

   45 :   -4.341E+00    47.22     -1.211E+01  42  Successfully solved 

   46 :   -4.341E+00    47.22     -1.211E+01  43  Successfully solved 

   47 :   -4.341E+00    47.22     -1.211E+01  44  Successfully solved 

   48 :   -4.341E+00    47.22     -1.211E+01  45  Successfully solved 

   49 :   -4.341E+00    47.22     -1.211E+01  46  Successfully solved 

   50 :   -4.341E+00    47.22     -1.211E+01  47  Successfully solved 

   51 :   -4.341E+00    47.22     -1.211E+01  48  Successfully solved 

   52 :   -4.341E+00    47.22     -1.211E+01  49  Successfully solved 

   53 :   -4.341E+00    47.22     -1.211E+01  50  Successfully solved 

   54 :   -4.341E+00    47.22     -1.211E+01  51  Successfully solved 

   55 :   -4.341E+00    47.22     -1.211E+01  52  Successfully solved 

   56 :   -4.341E+00    47.22     -1.211E+01  53  Successfully solved 

   57 :   -4.341E+00    47.22     -1.211E+01  54  Successfully solved 

   58 :   -4.341E+00    47.22     -1.211E+01  55  Successfully solved 

   59 :   -4.341E+00    47.22     -1.211E+01  56  Successfully solved 

   60 :   -4.341E+00    47.22     -1.211E+01  57  Successfully solved 

   61 :   -4.341E+00    47.22     -1.211E+01  58  Successfully solved 

   62 :   -4.341E+00    47.22     -1.211E+01  59  Successfully solved 

   63 :   -4.341E+00    47.22     -1.211E+01  60  Successfully solved 

   64 :   -4.341E+00    47.22     -1.211E+01  61  Successfully solved 

   65 :   -4.341E+00    47.22     -1.211E+01  62  Successfully solved 

   66 :   -4.341E+00    47.22     -1.211E+01  63  Successfully solved 

   67 :   -4.341E+00    47.21     -1.211E+01  64  Successfully solved 

   68 :   -4.341E+00    47.21     -1.211E+01  65  Successfully solved 

   69 :   -4.341E+00    47.21     -1.211E+01  66  Successfully solved 

   70 :   -4.341E+00    47.21     -1.211E+01  67  Successfully solved 

   71 :   -4.341E+00    47.19     -1.210E+01  68  Successfully solved 

   72 :   -4.341E+00    47.19     -1.210E+01  69  Successfully solved 

   73 :   -4.341E+00    47.19     -1.210E+01  70  Successfully solved 

   74 :   -4.341E+00    47.19     -1.210E+01  71  Successfully solved 

   75 :   -4.341E+00    47.17     -1.209E+01  72  Successfully solved 

   76 :   -4.341E+00    47.17     -1.209E+01  73  Successfully solved 

   77 :   -4.341E+00    47.17     -1.209E+01  74  Successfully solved 

   78 :   -4.341E+00    47.17     -1.209E+01  75  Successfully solved 

   79 :   -4.341E+00    47.08     -1.206E+01  76  Successfully solved 

   80 :   -4.341E+00    47.08     -1.206E+01  77  Successfully solved 

   81 :   -4.341E+00    47.07     -1.206E+01  78  Successfully solved 

   82 :   -4.341E+00    47.07     -1.206E+01  79  Successfully solved 

   83 :   -4.341E+00    47.06     -1.206E+01  80  Successfully solved 

   84 :   -4.341E+00    47.06     -1.206E+01  81  Successfully solved 

   85 :   -4.341E+00    47.06     -1.206E+01  82  Successfully solved 

   86 :   -4.341E+00    47.06     -1.206E+01  83  Successfully solved 

   87 :   -4.341E+00    47.05     -1.206E+01  84  Successfully solved 

   88 :   -4.341E+00    47.05     -1.206E+01  85  Successfully solved 

   89 :   -4.341E+00    47.04     -1.205E+01  86  Successfully solved 

   90 :   -4.341E+00    47.04     -1.205E+01  87  Successfully solved 

   91 :   -4.341E+00    47.04     -1.205E+01  88  Successfully solved 

   92 :   -4.341E+00    47.04     -1.205E+01  89  Successfully solved 

   93 :   -4.341E+00    47.03     -1.205E+01  90  Successfully solved 

   94 :   -4.341E+00    47.03     -1.205E+01  91  Successfully solved 

   95 :   -4.341E+00    47.03     -1.205E+01  92  Successfully solved 

   96 :   -4.341E+00    47.03     -1.205E+01  93  Successfully solved 

   97 :   -4.341E+00    47.02     -1.205E+01  94  Successfully solved 

   98 :   -4.341E+00    47.02     -1.205E+01  95  Successfully solved 

   99 :   -4.341E+00    47.02     -1.205E+01  96  Successfully solved 

  100 :   -4.341E+00    47.02     -1.205E+01  97  Successfully solved 

  101 :   -4.341E+00    47.01     -1.204E+01  98  Successfully solved 

  102 :   -4.341E+00    47.01     -1.204E+01  99  Successfully solved 

  103 :   -4.341E+00    47.00     -1.204E+01  100  Successfully solved 

  104 :   -4.341E+00    47.00     -1.204E+01  101  Successfully solved 

  105 :   -4.341E+00    47.00     -1.204E+01  102  Successfully solved 

  106 :   -4.341E+00    47.00     -1.204E+01  103  Successfully solved 

  107 :   -4.341E+00    47.00     -1.204E+01  104  Successfully solved 

  108 :   -4.341E+00    47.00     -1.204E+01  105  Successfully solved 

  109 :   -4.341E+00    47.00     -1.204E+01  106  Successfully solved 

  110 :   -4.341E+00    47.00     -1.204E+01  107  Successfully solved 

  111 :   -4.341E+00    46.99     -1.204E+01  108  Successfully solved 

  112 :   -4.341E+00    46.99     -1.204E+01  109  Successfully solved 

  113 :   -4.341E+00    46.99     -1.204E+01  110  Successfully solved 

  114 :   -4.341E+00    46.99     -1.204E+01  111  Successfully solved 

  115 :   -4.341E+00    46.99     -1.204E+01  112  Successfully solved 

  116 :   -4.341E+00    46.99     -1.204E+01  113  Successfully solved 

  117 :   -4.341E+00    46.99     -1.204E+01  114  Successfully solved 

  118 :   -4.341E+00    46.99     -1.204E+01  115  Successfully solved 

  119 :   -4.341E+00    46.99     -1.204E+01  116  Successfully solved 

  120 :   -4.341E+00    46.99     -1.204E+01  117  Successfully solved 

  121 :   -4.341E+00    46.98     -1.203E+01  118  Successfully solved 

  122 :   -4.341E+00    46.98     -1.203E+01  119  Successfully solved 

  123 :   -4.341E+00    46.98     -1.203E+01  120  Successfully solved 

  124 :   -4.341E+00    46.98     -1.203E+01  121  Successfully solved 

  125 :   -4.341E+00    46.97     -1.203E+01  122  Successfully solved 

  126 :   -4.341E+00    46.97     -1.203E+01  123  Successfully solved 

  127 :   -4.341E+00    46.97     -1.203E+01  124  Successfully solved 

  128 :   -4.341E+00    46.97     -1.203E+01  125  Successfully solved 

  129 :   -4.341E+00    46.97     -1.203E+01  126  Successfully solved 

  130 :   -4.341E+00    46.97     -1.203E+01  127  Successfully solved 

  131 :   -4.341E+00    46.97     -1.203E+01  128  Successfully solved 

  132 :   -4.341E+00    46.97     -1.203E+01  129  Successfully solved 

  133 :   -4.341E+00    46.97     -1.203E+01  130  Successfully solved 

  134 :   -4.341E+00    46.97     -1.203E+01  131  Successfully solved 

  135 :   -4.341E+00    46.96     -1.203E+01  132  Successfully solved 

  136 :   -4.341E+00    46.96     -1.203E+01  133  Successfully solved 

  137 :   -4.341E+00    46.95     -1.203E+01  134  Successfully solved 

  138 :   -4.341E+00    46.95     -1.203E+01  135  Successfully solved 

  139 :   -4.341E+00    46.94     -1.202E+01  136  Successfully solved 

  140 :   -4.341E+00    46.94     -1.202E+01  137  Successfully solved 

  141 :   -4.341E+00    46.88     -1.200E+01  138  Successfully solved 

  142 :   -4.341E+00    46.88     -1.200E+01  137  Infeasible problem 

  143 :   -4.341E+00    46.84     -1.199E+01  136  Infeasible problem 

  144 :   -4.341E+00    46.84     -1.199E+01  137  Successfully solved 

  145 :   -4.341E+00    46.84     -1.199E+01  138  Successfully solved 

  146 :   -4.341E+00    46.84     -1.199E+01  139  Successfully solved 

  147 :   -4.341E+00    46.84     -1.199E+01  140  Successfully solved 

  148 :   -4.341E+00    46.84     -1.199E+01  141  Successfully solved 

  149 :   -4.341E+00    46.81     -1.198E+01  142  Successfully solved 

  150 :   -4.341E+00    46.81     -1.198E+01  143  Successfully solved 

  151 :   -4.341E+00    46.79     -1.197E+01  144  Successfully solved 

  152 :   -4.341E+00    46.79     -1.197E+01  145  Successfully solved 

  153 :   -4.341E+00    46.77     -1.197E+01  146  Successfully solved 

  154 :   -4.341E+00    46.77     -1.197E+01  147  Successfully solved 

  155 :   -4.341E+00    46.76     -1.197E+01  148  Successfully solved 

  156 :   -4.341E+00    46.76     -1.197E+01  149  Successfully solved 

  157 :   -4.341E+00    46.74     -1.196E+01  150  Successfully solved 

  158 :   -4.341E+00    46.74     -1.196E+01  149  Infeasible problem 

  159 :   -4.341E+00    46.72     -1.195E+01  150  Successfully solved 

  160 :   -4.341E+00    46.72     -1.195E+01  149  Infeasible problem 

  161 :   -4.341E+00    46.54     -1.190E+01  148  Infeasible problem 

  162 :   -4.341E+00    46.54     -1.190E+01  149  Successfully solved 

  163 :   -4.341E+00    46.54     -1.190E+01  150  Successfully solved 

  164 :         -Inf      Inf           -Inf   0  Unbounded objective function 

+ 164 Finishing.  Cost: -Inf

ans =

     2

ans =

  -1.0000e-04

No matter how tight I set the inttol, I still get the same "INF" error...

[Johan Löfberg]

You are running a version of Mosek which has a bug which causes this unbounded node. I reported this to them this morning, and they have already fixed it. I don't know if the fix is available in public beta 7 yet, but try to download Mosek again and reinstall.

[Yuting Chen]

Wow, they're responding quite quickly!

I downloaded the newest version from their website and it is still the same old version... Anywhere I can get the most up-to-date source?

[Johan Löfberg]

I guess you have to wait for them to relase it.

Until then, simply edit bnb.m to account for this issue

Search for the line starting with output = bnb_solvelower

After that line, add

        if output.problem == 2 & ~isinf(lower)
            % Solver must have made a mistake
             output.problem = 1;            
        end

[Yuting Chen]

Thanks, Johan. It there anyway for you to share the updated file for Mosek with me ? :-)

[Johan Löfberg]

No, you would have to contact sup...@mosek.com. Otherwise, just use the fix I outlined and it will work equivalently.

[Yuting Chen]

I modified bnb.m as you suggested, however after 800+ iterations it returns the following error information:

 813 :   -4.534E+00    43.42     -1.149E+01  712  Successfully solved 

  814 :   -4.534E+00    43.42     -1.149E+01  713  Successfully solved 

  815 :   -4.534E+00    43.42     -1.149E+01  714  Successfully solved 

  816 :   -4.534E+00    43.42     -1.149E+01  715  Successfully solved 

  817 :   -4.534E+00    43.41     -1.149E+01  716  Successfully solved 

  818 :   -4.534E+00    43.41     -1.149E+01  717  Successfully solved 

  819 :   -4.534E+00    43.41     -1.149E+01  718  Successfully solved 

  820 :   -4.534E+00    43.41     -1.149E+01  719  Successfully solved 

  821 :   -4.534E+00    43.41     -1.149E+01  720  Successfully solved 

  822 :   -4.534E+00    43.41     -1.149E+01  721  Successfully solved 

  823 :   -4.534E+00    43.41     -1.149E+01  722  Successfully solved 

  824 :   -4.534E+00    43.41     -1.149E+01  723  Successfully solved 

  825 :   -4.534E+00    43.41     -1.149E+01  724  Successfully solved 

  826 :   -4.534E+00    43.41     -1.149E+01  725  Successfully solved 

  827 :   -4.534E+00    43.40     -1.149E+01  726  Successfully solved 

  828 :   -4.534E+00    43.40     -1.149E+01  725  Infeasible problem 

  829 :   -4.534E+00    43.40     -1.149E+01  726  Successfully solved 

  830 :   -4.534E+00    43.40     -1.149E+01  727  Successfully solved 

  831 :   -4.534E+00    43.40     -1.149E+01  728  Successfully solved 

  832 :   -4.534E+00    43.40     -1.149E+01  729  Successfully solved 

  833 :   -4.534E+00    43.38     -1.148E+01  730  Successfully solved 

  834 :   -4.534E+00    43.38     -1.148E+01  731  Successfully solved 

  835 :   -4.534E+00    43.38     -1.148E+01  732  Successfully solved 

  836 :   -4.534E+00    43.48     -1.151E+01  733  Unknown problem in solver (try using 'debug'-flag in sdpsettings) 

Reference to non-existent field 'sol'.

Error in callmosek>call_mosek_sdp (line 389)

x = res.sol.itr.y;

Error in callmosek (line 28)

    [x,D_struc,problem,res,solvertime,prob] = call_mosek_sdp(interfacedata);

Error in bnb_solvelower (line 128)

            output = feval(lowersolver,p);

Error in bnb>branch_and_bound (line 605)

        output = bnb_solvelower(lowersolver,relaxed_p,upper+abs(upper)*1e-2+1e-4,lower);

Error in bnb (line 279)

[x_min,solved_nodes,lower,upper,profile,diagnostics] = branch_and_bound(p,pss);

Error in solvesdp (line 355)

    eval(['output = ' solver.call '(interfacedata);']);

Error in MIP_SDP_Yuting_0520 (line 52)

info = solvesdp(F, -f'*x,ops);

could it be anything related to my settings for Mosek?

[Erling D. Andersen]

We have updated MOSEK now. You can grab it at

  http://www.mosek.com/download/

If it does not solve the problem then contact us at sup...@mosek.com.