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, 2020 at 11:41
  • $\begingroup$ Maybe $c_t$ is a typo for $z_t$? $\endgroup$
    – RobPratt
    Oct 14, 2020 at 13:02
  • $\begingroup$ Ah, that makes a lot of sense. Thanks. $\endgroup$
    – Sune
    Oct 14, 2020 at 16:50

1 Answer 1

5
$\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, 2020 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, 2020 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, 2020 at 9:06
  • $\begingroup$ Yes indeed $O(n^3)$ for the constraints, because of constraints 2 and 3. $\endgroup$
    – Kuifje
    Oct 14, 2020 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, 2020 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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