2
$\begingroup$

As far as I know, when we talk about the term of complexity, it referred to the time complexity of the model in which how long does it take to solve a specific mathematical program by a specific algorithm. For example, solving a knapsack problem by using dynamic programming takes $O(N\cdot W)$. Now, I would like to know about the model complexity in contrast to the time complexity. I was wondering if:

  • Is there any specific relationship between these two?
  • Is there any standard way to understand the complexity of the model, specifically, mixed-integer linear programming?
  • Is it that fact if the complexity of the model is high (I do not know the term "high" might be true) then, it would not be a polynomial algorithm to solve such a problem?
$\endgroup$
6
  • 1
    $\begingroup$ How do you define "model complexity"? $\endgroup$
    – prubin
    Oct 10 at 15:24
  • $\begingroup$ @Prof. Rubin, this is exactly what I am trying to know. As I have seen that in some where. 🙏 $\endgroup$
    – A.Omidi
    Oct 10 at 17:04
  • $\begingroup$ I can think of two aspects of complexity. (I imagine there are more.) One is just the size of the model (number of variables, number of constraints), which parameterizes time complexity. The other is the degree to which you are doing something offbeat or "funky" (column generation, decomposition, ...), which really can't be quantified. $\endgroup$
    – prubin
    Oct 10 at 19:53
  • $\begingroup$ @Prof. Rubin, thanks for your interesting comments. I think, what I am looking for is based on your first comment. (That I was not finding any reference about it). Would you please, share your idea a bit more about that? (specifically, on my first and second questions). Ah, just for clarifying, is "the model complexity" the correct term or weird? $\endgroup$
    – A.Omidi
    Oct 11 at 7:38
  • 1
    $\begingroup$ I would not call the phrase "model complexity" weird; it's just a bit vague. Consider your reference to time complexity $O(N\cdot W)$ in your question. That indicates time grows linearly with the two dimensions $N$ and $W$. In a more complicated model (where you had $N^2$ variables or $N\cdot W^2$ constraints or whatever, the time complexity would be a higher order function of the dimensions. $\endgroup$
    – prubin
    Oct 11 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.