MILP worst-case Complexity order
Answered
Hello, I have a SOCP in my paper and I am using Gurobi to solve it. the problem is a MILP. I need to compute the complexity order of my algorithm to be included in the paper. Can I have the information regarding the complexity of the algorithms Gurobi uses for solving MILP?
-
I am a bit confused by your statement.
I have a SOCP in my paper and I am using Gurobi to solve it. the problem is a MILP.
Is it a SOCP or a MILP? Or do you mean that you have second order cone constraints and integers?
Can I have the information regarding the complexity of the algorithms Gurobi uses for solving MILP?
(Mixed) Integer Programming is NP-complete so I don't understand what you expect here. I would guess that you would like to know the complexity of a general B&B algorithm which has a worst case exponential time complexity.
0 -
Hello Jaromil,
Sorry for my bad explanation. Yes, the scenario is that my problem is SOCP while some of the variables are integer. I understand your comment that the MIP has exponential time complexity. So, I would like to know if in this case, Gurobi considers MIP complexity as the dominant cost or we can also refer to the SOCP?
0 -
So, I would like to know if in this case, Gurobi considers MIP complexity as the dominant cost or we can also refer to the SOCP?
Yes, the MIP complexity dominates, since LPs are a subset of SOCPs (they are SOCPs without any second order constraints). And MIP uses LPs to solve subproblems of the B&B tree. Now, when you have an SOCP model with integer variables, you can use a B&B algorithm and solve continuous SOCP relaxations. The B&B algorithm still has an exponential worst case complexity.
If however, your model has some specific structure or there is any information you might exploit to limit the integer complexity such as limiting the number of possible integer values instead of enumerating every possible combination. For example let's say, that for whatever reason, you know that your integer variables can attain only \(n^2\) combinations where \(n\) is the number of integer variables instead of the usual combinatorial explosion, then you might still end up with a polynomial time algorithm (as long as you use a polynomial time algorithm to solve your SOCPs).
0
Please sign in to leave a comment.
Comments
3 comments