Skip to main content

Computational complexity of MILP vs MIQP model

Answered
Pieter Degeling
  • Gurobi-versary
  • First Question
  • First Comment

Dear,

I was wondering about the inherent computational complexity of MIQP vs MILP models.
I am not sure if the following formulation is correct, but:
If we assume that there are two models consisting of equal number of constraints and variables, could it be said that MIQP is inherently more computationally expensive?
If so, can this be substantiated?

 

Thanks in advance,
Pieter

Related to

1

Comments

7 comments

Date Votes
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Pieter,

    If we assume that there are two models consisting of equal number of constraints and variables, could it be said that MIQP is inherently more computationally expensive?
    If so, can this be substantiated?

    The number of variables or constraints is not the correct way to distinguish which model type is more difficult to solve. The reason is that it is possible to solve some huge MIQPs while it is almost impossible to solve some small MILPs.

    A good argument to distinguish complexity of model classes is to note that the set of all MILP problems is a subset of all MIQP problem. This is because every MILP is an MIQP without quadratic terms. However, it is not possible to formulate every MIQP as a MILP. So in terms of complexity one could say that MIQPs are harder than MILPs.

    For MIQPs, one would also have to distinguish between convex and nonconvex objective functions. MIQPs with a convex objective function are a subset of MIQPs with a nonconvex objective function. In terms of complexity, this would mean that nonconvex MIQPs are harder than convex MIQPs.

    Please note that this does not mean that solving MIQPs is always harder than solving MILPs.

    Best regards, 
    Jaromił

    1
  • Pieter Degeling
    Edited
    • Gurobi-versary
    • First Question
    • First Comment

    Hi Jaromił,
    Thanks for the extensive answer. I am not sure if it really answers my question, let me try to rephrase.

    I have developed a model with one quadratic constraint. It is a model used to simulate energy consumption of a fuel cell. The only quadratic constraint is power = voltage * current, where all three are continuous variables, and voltage is linearly dependent on current. In other words, P(t)= V(t) * I(t) = a*I(t)^2 - b*I(t)
    If we were to replace the voltage-current relation (V(t) = a -b*I(t) ) by a constant voltage in my model, resulting in a linear relation between power and current and thus a MILP model, the optimal solution can be found almost 1000 times faster.
    I was wondering how I can explain that for similar models, the linear model is faster than its quadratic counterpart.
    Could you shed some light on this, or is this not enough information?

    Thanks,

    Pieter

    1
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Pieter,

    Nonconvex (quadratic) models, especially found in the Power industry, are well known for their extreme complexity. The main difficulty for these models are caused by the nonconvex continuous terms. The discrete variables are often not many or they have some special structure which can be exploited and thus often do not contribute much to the model's complexity. For this reason, when you linearize all the nonconvex terms, you basically take all the complexity away from the model.

    On a side note: It is common practice to use linear approximation for models in the power industry and speed-ups of 1000x+ are commonly seen when switching from a nonlinear nonconvex model to its linear approximation. A very good example for this is the alternate current optimal power flow (ACOPF) model and its linear approximation version, the direct current optimal power flow (DCOPF) model. Medium to large ACOPF models cannot be solved to global optimality, however their linear approximation as DCOPF are solved thousand of times in practice every day. Please note that the word "global" is of importance here, since local solvers can find (good) feasible solutions even for very large ACOPF models.

    I hope this helps.

    Best regards, 
    Jaromił

    1
  • Pieter Degeling
    • Gurobi-versary
    • First Question
    • First Comment

    Hi Jaromił,

    Thanks again for this extensive answer. I chose to include the quadratic function because, in my view, the linearization led to a significant error. I do indeed have a nonconvex continuous term as a result

    The main thing I am wondering about is what exactly causes the increase in complexity stemming from the nonconvex quadratic equality constraint. It would be great if you could help me with this.
    Thank you so much.

    Best regards,

    Pieter

    1
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff
    Edited

    Hi Pieter,

    The main thing I am wondering about is what exactly causes the increase in complexity stemming from the nonconvex quadratic equality constraint. It would be great if you could help me with this.
    Thank you so much.

    For convex continuous models, it is guaranteed that every minimum is also the global minimum of the model.

    For nonconvex models, it is not the case. This means, that there can be multiple local minima. So there are two difficulties. You have to somehow find very good feasible points which is a field of research on its own. Additionally, once you have found a good feasible solution, it is necessary to provide some proof of global optimality. Otherwise, you cannot know how good the solution you found actually is. The idea Gurobi uses to provide such a proof is the spatial B&B algorithm. I would recommend having a look at our Nonconvex webinar and Nonconvex Tech Talk for additional details about the B&B algorithm.

    Please note that the above does not mean that convex optimization is easy. It just tries to explain the complexity difference in the most understandable way.

    Best regards, 
    Jaromił

    1
  • Pieter Degeling
    • Gurobi-versary
    • First Question
    • First Comment

    Hi Jaromił,

    Thank you so much for your clear answers. I will definitely have a look at the webinar and the tech talk!
    I do have one last question, which is about the local minima.
    I have one quadratic constraint, of the form P=c*I^2-b*I.
    By constraining I to be non-negative, doesn't this prevent multiple local minima?
    Or can local minima still be available due to the interaction with all the other linear constraints.
    Thank you so much.

    Kind regards,
    Pieter

    1
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Pieter,

    I have one quadratic constraint, of the form P=c*I^2-b*I.
    By constraining I to be non-negative, doesn't this prevent multiple local minima?
    Or can local minima still be available due to the interaction with all the other linear constraints.

    It depends on the rest of your model. In particular it depends on the correlation of the nonconvex constraint with the discrete variables and other nonlinear parts of your model. My guess without knowing the rest of your model would be that if P=c*I^2-b*I is the only nonconvex constraint in your model, then the complexity of the model and time needed to optimize the model should not shoot up too much, but this is just a gut feel which can be completely wrong. If P=c*I^2-b*I is the only nonconvex constraint, you could think about whether it is valid to make it an inequality constraint. For example, the constraint P >= c*I^2-b*I is convex for c >= 0 and would simplify the model a lot.

    Best regards, 
    Jaromił

     

     

    1

Please sign in to leave a comment.

Didn't find what you were looking for?

New post