# What's the most scalable solver of this problem?

Consider the following optimisation problem that its size is parameterised by $$n$$ (width) and $$m$$ (depth):

Find $$w_1, w_2, \ldots, w_n$$ that minmises: $$\min \Big[w_1x_1^0 + w_2x_2^0 + \ldots + w_nx_n^0 \Big]$$

Subject to:

$$b^1_{\min} \le w_1x_1^1 + w_2x_2^1 + \ldots + w_nx_n^1 \le b^1_{\max}$$ $$b^2_{\min} \le w_1x_1^2 + w_2x_2^2 + \ldots + w_nx_n^2 \le b^2_{\max}$$ $$\vdots$$ $$b^m_{\min} \le w_1x_1^m + w_2x_2^m + \ldots + w_nx_n^m \le b^m_{\max}$$

Where:

• $$w_1, w_2, \ldots, w_n$$ are variables that we must tune (by assigning real numbers to them) in order to solve the optimisation problem above.

• for any $$1 \le i \le n$$ and $$1 \le j \le m$$, $$x_i^j$$ is a constant real number, and $$b^j_{\min}, b^j_{\max}$$ are bounds.

Note that superscript $$^j$$ is not an exponent, but a second index. I thought it would be more readable to write $$x_i^j$$ than $$x_{i,j}$$.

Question: What's the best asymptotic worst run-time and space that we can get for a solver of this problem?

E.g. can it get as low as $$O(nm)$$? if not, what's the lowest we can achieve?

Any instance of linear programming can be represented in this form. For instance, minimize $$c^\top w$$ subject to $$Aw \le b$$ can be represented by setting $$b^i_\max = b_i$$, $$x^i_j = A_{i,j}$$, $$b^i_\min=-\infty$$, $$x^0_j=c_j$$. Therefore, you can't expect any special-case algorithm that is more efficient than general-purpose linear programming.