MISDP Truss Topology Problem

[TobiFx17]

Dear Prof.Johan Löfberg,

i hope you are doing well.

i am trying to implement the truss topology problem via a mixed integer semidefinite problem. I tried recreating 3 Examples from a research paper which are supposed to be solved by YALMIP. For each Example I created three instances where the Input data is in mm, cm and mm.

(so in theory they are equivalent but looking at the coefficients of the constraints mm seems to fit best). I tried solving them with 'cutsdp' + 'gurobi' and with 'bnb' + 'sedumi

Example 1

The first smaller scale Problem using 'bnb' delivers nearly the same optimal solution for all 3 instances (m, cm ,mm). On the other hand using 'cutsdp'  i get nearly the same solution as 'bnb' by using meters. But when using the cm and mm examples it delivers the same optimal solution but they differ from the first four delivered ones.

Example 2

The meter instance of the second example doesn't seem to work with 'bnb'. It immediately stops. And the other two instances (cm and mm) with 'bnb' and with 'cutsdp' i couldn't get a solution in reasonable time (maximal time i tried was 1800s). This is the biggest example with 98 bars.

Example 3 

First instance (meters) didnt work with 'bnb' -> ended immediately (infeasible). Other two instances with 'bnb'  and all three instances with 'cutsdp' didnt deliver a result after waiting about 5-10 min. 

I know that MISDP can be hard to solve and may take a while but what confuses me is that all the examples i am trying to recreate were stated to be solved in under 3 min. And im confused with 'bnb' saying that my problem is infeasible and even when i get results they differ. i know its a lot of text but i wanted to give examples to recreate. Is there maybe something wrong with my problem formulation or numerical errors are causing different results ? or are the problems to big to handle ?

i attached the files for you to recreate and to avoid having to copy a bunch of code from my commando window.

if you notice something let me know. Best regards Tobi

[Johan Löfberg]

With Mosek as the relaxations solver, bnb solves all 9 problems without issues with 1 and 2 solved almost instantly and 3 taking a minute or so to complete (cannot judge the correctness though, objective is not the same but computed bars are the same, scaled with factor 10)

With sedumi, there are way to many numerical issues for bnb to work. Did they really use sedumi in the paper?

>> Example_2_in_mm

* Starting YALMIP integer branch & bound.
* Lower solver : SeDuMi
* Upper solver : rounder
* Max time : 3600
* Max iterations : Inf
* Inital model: 122 binaries, 0 integers, 99 continuous.
* 573 linear rows, 2304 conic rows
* Starting presolve and model analysis

* Presolved model: 122 binaries, 0 integers, 99 continuous.
* 563 linear rows, 2304 conic rows
* 72 knapsacks (72 GUBs, 0 cardinality, 0 general)
Node Incumbent Gap Bound Open Cut Time Diagnostics

1 : Inf Inf% 0.000E+00 1 0/ 0 1.3 (0/1/1/93) Numerical problems, will try to recover.

2 : Inf Inf% 0.000E+00 1 0/ 0 2.4 (14/2/2/93) Numerical problems, will try to recover.

3 : Inf Inf% 0.000E+00 2 0/ 0 3.3 (15/2/2/93) Numerical problems, will try to recover.

4 : Inf Inf% 0.000E+00 3 0/ 0 4.1 (31/3/3/93) Numerical problems, will try to recover.

5 : Inf Inf% 0.000E+00 4 0/ 0 4.8 (31/4/4/91) Numerical problems, will try to recover.

6 : Inf Inf% 0.000E+00 5 0/ 0 5.4 (46/5/5/91) Node solved succesfully.

7 : Inf Inf% 0.000E+00 6 0/ 0 6.0 (59/5/5/75) Node solved succesfully.

8 : Inf Inf% 0.000E+00 7 0/ 0 6.4 (60/5/5/62) Node solved succesfully.

9 : Inf Inf% 0.000E+00 8 0/ 0 6.8 (69/5/5/61) Node solved succesfully. 

cutsdp does not seem to perform here at all, and appears to cut away optimal solutions early on sometimes. I suspect it has problematic numerics for the algorithm, but I will look into it as a test case.

[TobiFx17]

Thank you for your quick respond it was very helpful. Yes in the paper it was stated : "For comparison, the MISDP formulation, i.e., problem (23) with constraint (24), is solved with YALMIP [40]. YALMIP finds a global optimal solution of an MISDP problem with a branch-and-bound method, at each iteration of which an SDP problem is solved. We used YALMIP with the default setting, where SDP subproblems are solved with SeDuMi ver. 1.3 [48,53]."  Thats the reason i tried using 'bnb' + 'sedumi'. 

I tried bnb + mosek and it worked like a charm so thank very much for  your help. i didn't have Mosek installed and only tried SDPT3 instead of sedumi which didn't work either.

[Johan Löfberg]

The conclusion is that they used an old version of YALMIP which was more lenient to relaxation solver numerical problems (it accepted the solution as a lower bound). Current version is more strict and does not accept a solution with a numerical issue flag as a valid lower bound. SeDuMi and SDPT3 have far more numeircal issues with the models and will thus not work, in contrast to mosek which performs well.