How to determine the size of a model?

Question

I want to know about the number of variables and constraints of this formulation (exp: $o(n)$ variables and constraints or $o(n^2)$ ....).

Is the number of variables $\mathcal O(n^3)$ because we have three index variables with $N\times N\times N$?

How can I compute the complexity of the constraints step by step? I would be grateful if you have any other examples or references explaining this question.

Answer 1

You are correct, you have to look at the variables' ranges.

• $z_t$ is defined $\forall t \in T$, so you have $|T| \in O(|T|)$ such variables;
• $y_i^k$ is defined $\forall i \in [1,n], \; \forall k \in [1,n]$, so you have $n^2 \in O(n^2)$ such variables;
• $x_{ij}^k$ is defined $\forall (i,j) \in [1,n]\times [1,n], i < j, \; \forall k \in [1,n]$, so you have $\frac{n(n-1)}{2}n \in O(n^3)$ such variables;

So you end up with a total of $O(|T|)+ O(n^2) + O(n^3) = O(|T|)+ O(n^3)$ variables.

Likewise for constraints: you can see that you have $O(n^3)$ of them.