I have the following linear program: $$ \begin{array}{cc} \text{Maximize} & a^T x \\ \text{Subject to} & x_{\min} \leq x \leq x_{\max} \\ & \mathbf{1}^T x = 1 \end{array} $$ where $x \in \mathbb{R}^n$, $\mathbf{1}^T x$ denotes the sum of entries of $x$, and $a$ is known and has distinct strictly positive entries.
I am looking for a quick way to solve the above without using an LP solver. Is there a fast procedure to follow? (besides Simplex).
Thank you!
The optimal solution is the following: Set all variables equal to their minimums. Then, starting from the largest $a_i$ to the smallest, iteratively set the corresponding $x_i$ as large as possible until you hit $\sum_i x_i = 1$. If $\sum_i x_{i,min} > 1$ or $\sum_i x_{i,max} < 1$ then the problem is infeasible. I believe that this is the same solution that Geoffrey Irving's algorithm outputs.
The reason this works is that you can transform your problem into the LP relaxation of the 0-1 knapsack problem via $$y_i = \frac{x_i - x_{i,min}}{x_{i,max} - x_{i,min}}.$$
In $y$-variable space, the problem becomes \begin{array}{cl} \text{Maximize} & \sum_i c_i y_i \\ \text{Subject to} & 0 \leq y_i \leq 1, \text{ for each } i \\ & \sum_i b_i y_i = d, \end{array}
where $c_i = a_i (x_{i,max} - x_{i,min})$, $b_i = (x_{i,max} - x_{i,min})$, and $d = 1 - \sum_i x_{i,min}$. If the original problem is feasible then $d \geq 0$. The $c_i$'s and $b_i$'s are nonnegative, so we do have the LP relaxation of 0-1 knapsack. (The expression $\sum_i a_i x_{i,min}$ technically appears in the objective, too, but since it is a constant we can drop it.)
Assuming the variables are sorted by the ratio $\frac{c_i}{b_i} = a_i$ from largest to smallest, the known optimal solution is the greedy one: Set $y_1 = y_2 = \cdots = y_k = 1$ for as large a $k$ as possible, set $y_{k+1} = d - \sum_{i=1}^k b_i$, and set $y_{k+2} = \cdots = y_n = 0$. Transforming this solution back into the $x$-variable problem space gives the solution I just described.
In addition, 0-1 knapsack does have a $\leq$ constraint rather than an $=$ constraint. If you can fit all the items in the knapsack with space left over, then the original $x$-variable problem is infeasible because $\sum_i x_{i,max} < 1$.
The greedy algorithm works: start with some solution that satisfies your constraints, and then iteratively increase the $x_i$ with largest $a_i$ that isn't at $x_{\max}$ and shrink the $x_j$ with smallest $a_j$ that isn't at $x_{\min}$ as far as possible. Stop when no further pair motions are possible. This takes $O(n \log n)$ to sort $a$ and $O(n)$ time for the rest.
When the algorithm completes, there will be a set of $x_i$'s stuck at $x_{\max}$ (those with large $a_i$), a set of $x_j$'s stuck at $x_{\min}$ (those with small $a_j$), and at most one $x_k$ with $x_{\min} < x_k < x_{\max}$ and $a_i > a_k > a_j$. A differential change to $x$ starting from such a position cannot increase the objective, since any gains due to increasing $x_j$ or $x_k$ would be more than offset by losses due to decreasing $x_i$ or $x_k$.
