Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
Thank you for your answer! –  Mohammad Fawaz Dec 7 '12 at 17:13
    
@Fawaz: You're quite welcome. –  Mike Spivey Dec 7 '12 at 18:08
add comment

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

share|improve this answer
    
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. –  Arnold Neumaier Dec 6 '12 at 17:09
    
Thank you for your answer. The approach seems interesting but I second the request of @ArnoldNeumaier of providing an argument. –  Mohammad Fawaz Dec 6 '12 at 17:34
    
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. –  Geoffrey Irving Dec 6 '12 at 17:49
    
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. –  Arnold Neumaier Dec 6 '12 at 18:33
    
Ah, you're right about same at each iteration. Should be fixed now. –  Geoffrey Irving Dec 6 '12 at 21:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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