4
$\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$
3
  • 1
    $\begingroup$ Just out curiosity, what constrains the $z_t$ variables in this model? $\endgroup$
    – Sune
    Oct 14 '20 at 11:41
  • $\begingroup$ Maybe $c_t$ is a typo for $z_t$? $\endgroup$
    – RobPratt
    Oct 14 '20 at 13:02
  • $\begingroup$ Ah, that makes a lot of sense. Thanks. $\endgroup$
    – Sune
    Oct 14 '20 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.

$\endgroup$
12
  • $\begingroup$ Thanks, so for the constraints I should focus on the summation part of the constraint or the belonging part? $\endgroup$
    – fathese
    Oct 14 '20 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 '20 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 '20 at 9:06
  • $\begingroup$ Yes indeed $O(n^3)$ for the constraints, because of constraints 2 and 3. $\endgroup$
    – Kuifje
    Oct 14 '20 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 '20 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.