A linear objective function that achieves equal ratio allocation

[SouthEndMusic]

The objective function

@jarsarasty suggested the following linear objective function that also achieves equal ratio allocation.

Say we have demands $d_i$, allocated flows $F_i$, and the allocated fraction $f$. We want to achieve $F_i = f d_i$, and so we introduce the constraints

$$ u_i \ge F_i - f d_i, \quad l_i \ge f d_i -F_i $$

where $u_i, l_i \ge 0$ are the upper error and the lower error respectively. Then to minimize the error we minimize

$$ \sum_{i \in I} u_i + l_i. $$

This however penalizes absolute flow amounts, so if we want to penalize relative errors we either minimize

$$ \sum_{i \in I} \frac{u_i + l_i}{d_i}, $$

or use in stead of the above the constraints

$$ u_i \ge \frac{F_i}{d_i} - f, \quad l_i \ge f-\frac{F_i}{d_i} $$

(which I think is nicest).

My thoughts on this objective function

I like this concept a lot, because to me it is very explainable, more so than the first objective function that achieves equal ratio allocation. An added bonus that Jesús mentioned is that in general linear problems can be solved faster than quadratic problems.

The error behavior in this method is different from in the quadratic case, i.e. each incremental deviation from the target allocation is weighed equally. I think this makes the results also more explainable though, and we haven't had much feedback yet about how the optimization plays out when equal ratio allocation cannot be achieved.

The role of $f$ needs some more thought. In the current implementation this $f$ is not a priori known. We could compute it as (the minimum of $1$ and) the sum of the available source capacity over the sum of demands (within a priority). This however doesn't take the graph topology and constraining nodes into account. So ideally $0 \le f \le 1$ itself is also maximized, but then the question is how do we combine that with the objective above.

[SnippenE]

Paused until need of lineair function is asked for by users