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!


2 Answers 2


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$.

  • $\begingroup$ Please make this more precise. Your current method only changes two components of $x$, if taken literally, hence is not correct. It would also be nice to give an argument why the final result is optimal. $\endgroup$ Commented Dec 6, 2012 at 17:09
  • $\begingroup$ Thank you for your answer. The approach seems interesting but I second the request of @ArnoldNeumaier of providing an argument. $\endgroup$ Commented Dec 6, 2012 at 17:34
  • $\begingroup$ It changes two components per iteration, so I'm not sure what you mean by not correct if taken literally. I'll add a brief explanation. $\endgroup$ Commented Dec 6, 2012 at 17:49
  • $\begingroup$ Well, the $x_i$ with largest $i$ is the same at each iteration, etc. So you attempt to change the same two components repeatedly. Your new version is irritating as the index labels $ij$ apparently mean different things in the two paragraphs. $\endgroup$ Commented Dec 6, 2012 at 18:33
  • $\begingroup$ Ah, you're right about same at each iteration. Should be fixed now. $\endgroup$ Commented Dec 6, 2012 at 21:50

Your Answer

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

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