5
$\begingroup$

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. enter image description here

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

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, so for the constraints I should focus on the summation part of the constraint or the belonging part? $\endgroup$ – fathese Oct 14 at 8:54
  • $\begingroup$ It is not $o(n^3)$ for the constraints because we have used $i$, $j$ and $k$? $\endgroup$ – fathese Oct 14 at 9:00
  • $\begingroup$ the belonging part. because each item of the "belonging part" is a distinct line (a separate constraint). $\endgroup$ – Kuifje Oct 14 at 9:06
  • $\begingroup$ Yes indeed $O(n^3)$ for the constraints, because of constraints 2 and 3. $\endgroup$ – Kuifje Oct 14 at 9:08
  • $\begingroup$ 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 ? $\endgroup$ – fathese Oct 14 at 9:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.