<p>It can be solved in different ways.</p>
<p>A classic approach is the Simplex method from the late Dr. George Dantzig.</p>
<p>It can be implemented in the tabular form, or using (numerical) linear algebra.</p>
<p>For the linear algebraic approach, the classic matrix equation <span class="math-container">$Ax = b$</span> is formulated from its objective function and the constraints.</p>
<p>The computation <span class="math-container">$Ax = b$</span> is determined by the size of matrix <span class="math-container">$A$</span>, which is influenced by the number of decision variables and constraints. Hence, the size of the matrix is bound by the number of variables, due to the rules of linear algebra, such as multiplication rules for matrices as well as between a matrix and a vector. You can arbitrarily add more constraints, but it will not help solve the problem.</p>
<p>Reference:
<a href="https://en.wikipedia.org/wiki/Linear_programming#Current_matrix_multiplication_time_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Linear_programming#Current_matrix_multiplication_time_algorithm</a></p>
<p>So, you are right that the computational complexity of algorithms to solve linear programming problems can be expressed as a function of &quot;m&quot; and &quot;n&quot;, such as <span class="math-container">$O(mn)$</span>. However, in the 20th century, they just picked the larger of the two dimensions, and characterize the problem based on that.</p>
<p>The homework problems that I worked on has <span class="math-container">$n &gt; m$</span>.</p>

CC BY-SA 4.0
2024-10-17T08:51:42.600Z
2024-10-17T08:51:42.600Z
Giovanni
<p>What is the computational complexity of solving a linear program with m constraints in n variables?</p>
<p>I found some arguments that it is O(n^3), but wouldn't it be related to the number of constraints as well?</p>

CC BY-SA 4.0
2024-10-15T14:14:59.500Z
There are many algorithms for linear programming, and they tend to have different run-time bounds.  So I wouldn't say the problem is known to have a specific complexity.  If you ask about a particular algorithm, the question would be easier to answer (or you could just search the literature for the best bounds known for the algorithm).
Neal Young
<time-complexity><linear-programming>
the computational complexity of solving a linear program with m constraints in n variables
Moonie
# the computational complexity of solving a linear program with m constraints in n variables

(Asked by: username_0 on 2024-10-12)

What is the computational complexity of solving a linear program with m constraints in n variables?

I found some arguments that it is O(n^3), but wouldn't it be related to the number of constraints as well?

**Tags:** time-complexity, linear-programming
> **Comments:**
> **username_1**: There are many algorithms for linear programming, and they tend to have different run-time bounds.  So I wouldn't say the problem is known to have a specific complexity.  If you ask about a particular algorithm, the question would be easier to answer (or you could just search the literature for the best bounds known for the algorithm).  

---

## 1 answers

### Answer by username_2 on 2024-10-17. Score: -3

It can be solved in different ways.

A classic approach is the Simplex method from the late Dr. George Dantzig.

It can be implemented in the tabular form, or using (numerical) linear algebra.

For the linear algebraic approach, the classic matrix equation $Ax = b$ is formulated from its objective function and the constraints.

The computation $Ax = b$ is determined by the size of matrix $A$, which is influenced by the number of decision variables and constraints. Hence, the size of the matrix is bound by the number of variables, due to the rules of linear algebra, such as multiplication rules for matrices as well as between a matrix and a vector. You can arbitrarily add more constraints, but it will not help solve the problem.

Reference:
<https://en.wikipedia.org/wiki/Linear_programming#Current_matrix_multiplication_time_algorithm>

So, you are right that the computational complexity of algorithms to solve linear programming problems can be expressed as a function of "m" and "n", such as $O(mn)$. However, in the 20th century, they just picked the larger of the two dimensions, and characterize the problem based on that.

The homework problems that I worked on has $n > m$.


---

