# How to determine the size of a model?

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.

• Just out curiosity, what constrains the $z_t$ variables in this model? – Sune Oct 14 at 11:41
• Maybe $c_t$ is a typo for $z_t$? – RobPratt Oct 14 at 13:02
• Ah, that makes a lot of sense. Thanks. – Sune Oct 14 at 16:50

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.

• Thanks, so for the constraints I should focus on the summation part of the constraint or the belonging part? – fathese Oct 14 at 8:54
• It is not $o(n^3)$ for the constraints because we have used $i$, $j$ and $k$? – fathese Oct 14 at 9:00
• the belonging part. because each item of the "belonging part" is a distinct line (a separate constraint). – Kuifje Oct 14 at 9:06
• Yes indeed $O(n^3)$ for the constraints, because of constraints 2 and 3. – Kuifje Oct 14 at 9:08
• Could a formulation like this with o(n3) variables and constraints consume less execution time than a flow formulation with o(n2) variables and constraints ? – fathese Oct 14 at 9:52