What is a "good enough" method of assigning values to n variables subject to basic bounding constraints while maintaining relative weights?

Question

Given triples of $n$ floating point values

$$(\min_1, \max_1, w_1), \dots, (\min_n, \max_n, w_n)$$

and a value $V$, what is a good algorithhm to assign values $v_i$ to each of the triples such that the following conditions hold?

1. $\min_i \le v_i \le \max_i$.
2. $\displaystyle\sum_{i=1}^n v_i = V$.
3. $\dfrac{v_i}{V}$ is as close as possible to $\dfrac{w_i}{W}$, where $W = \displaystyle\sum_{i=1}^n w_i$, i.e., minimize $\displaystyle\sum_{i=1}^n \left| \frac{v_i}{V} - \frac{w_i}{W} \right|$.

I understand the above can be solved via an LP solver but am looking for an algorithm that may not return the optimal assignment but that is deterministic, returns close to the optimum solutions, runs in $O(n)$ time, and returns solutions that are stable in the sense that if two instances of the problem definition are "close to each other" then the solutions tend to be close to each other.

It seems like there should be a greedy approach the performs sufficiently in which the first step is assigning the minima to $v_i$ and then proportioning out the "slack" but I am not sure how to deal with the maxima while doing this.

Answer 1

(This answer is the work of Michal Forišek ... I will paraphrase here)

First reformulate the problem by nomalizing the constraints and weights yielding:

• $\sum v_i = 1$
• $\forall i: \min_i \leq v_i \leq \max_i$
• minimize $\sum |v_i - w_i |$

Note that the problem is only solvable if $\sum \min_i \leq 1 \leq \sum \max_i$. Then find an optimal solution as follows:

1. Set each $v_i$ equal to $w_i$. If this is a valid solution, we are done.

2. For each $i$, if $v_i < \min_i$, increment $v_i$ to $\min_i$.

3. For each $i$, if $v_i > \max_i$, decrement $v_i$ to $\max_i$.

4. While $\sum v_i < 1$, find the smallest $x$ such that $v_x$ that can be incremented and increment it until you either get $\sum v_i = 1$ or $v_x = \max_x$.

5. While $\sum v_i > 1$, do the same but decrement.

The above will be optimal but Michal notes that one might get intuitively better results by minimizing the sum of squares rather than of absolute values, which is possible to do by modifying 4. and 5. above.