solution speed for a large scale MISOCP problem with 100 000 SOCP constraint and 1000 binary variable and 10 000 continuous varible

[Yang]

hello everyone,

Has anyone solved a large-scale MISOCP problem with 100 000 SOCP constraints and 1000 binary variables and 10 000 continuous variables? where the socp constraint only involves continuous variables.   How long does it takes for the solvers such as Gurobi or Cplex to solve the problem?

Thanks!

[Johan Löfberg]

Expected solutiontime is Inf, if you are lucky you might be ale to solve it days, if you are luckier than most and it is a trivial problem it might be solved in hours/minutes/seconds.

To summarize: the proof is in the pudding, i.. you won't know without testing.

https://yalmip.github.io/slowmilp

[Yang]

Thanks, Prof. Johan. What if we reduce the integer variables to 100? Actually, what I am worrying about most is the SOCP constraint. Will the SOCP constraint brings lots of computational burdens?

[Johan Löfberg]

As it is described in the link I gave you, if you have a super fast implementation and computer, already 72 binary variables can take the age of the universe to complete. You cannot say anything without testing when it comes to integer programs (the only thing you know is that it most likely takes inf years in theory, but many problems happens to be (relatively) simple to solve in practice)

[Yang]

well then, what if we neglect binary variables. will 100 000 SOCP constraints bring lots of computational burden? Thank you very much for the response.

[Johan Löfberg]

Depends on the structure. 100000 dense SOCP constraints in 1000 variables could be completely unsolvable, while very sparse it could probably be solved in seconds or at least minutes

Here is a 10^5 sized problem solved in 1 second. Trivial beyond sanity of course, but that's the point.

>> N = 100000;

>> x = sdpvar(2,N);

>> optimize(cone([ones(1,N);x]),sum(sum(x)))

    yalmipversion: '20200930'

    matlabversion: '9.9.0.1524771 (R2020b) Update 2'

       yalmiptime: 1.1608

       solvertime: 0.9222

             info: 'Successfully solved (MOSEK)'

          problem: 0

[Yang]

OK, understood. Cannot be more appreciated!

[Michal Adamaszek]

If you use MOSEK and dump the problem to a file (instructions: https://docs.mosek.com/9.2/faq/faq.html#how-do-i-dump-the-problem-to-a-file-to-attach-with-my-support-question) then you are welcome to share it with MOSEK support. We like to stress test the solver, and maybe we can help with tuning solver settings.