0

I am currently using a MILP calculation and I was wondering if anyone can recommend a more mathematically simplistic method of calculating this distribution and arriving at a similar result?

  • Qty - 15 shares
  • Range - 10-20
  • Target average price - <= 16 (Ideally as close as possible)
  • Distribution profile - 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 2 (from 10-20 results in 16 avg)

The above distribution achieves the desired result, but the nature of MILP calculations means they can be fairly computationally intensive and complex. I just haven't been able to find an alternative method of performing the same calculation and was hoping one of the bright minds here might have a suggestion.

user3033725
  • 29

1 Answers1

1

You didn't really state the problem, but this is what I think it is. You have positive integers $A < B$, $C$, $D$, and you want nonnegative integers $x_{A}, \ldots, x_{B}$ so that $\sum_i x_i = C$ and $\sum_i i x_i = D$ (or if that was not possible, you'd like it as close as possible). In your particular case, $A = 10$, $B=20$, $C=15$ and $D = 15 \times 16$.

There is a simple dynamical programming algorithm. For simplicity I'll do it for the case where you want equality, but it's not hard to adapt to the "as close as possible" case.

For $s = A \ldots B$, $t = 0 \ldots C$, $u = 0 \ldots D$ let $V(s,t,u) = 1$ if there exist $x_s, \ldots, x_{B}$ such that $\sum_{i=s}^B x_i = C - t$ and $\sum_{i=S}^B i x_i = D - u$, and $0$ otherwise. Then we have the recurrence

$$V(s,t,u) = \max \left\{ V(s+1, t + x, u + s x) \; :\; x = 0 \ldots \min(C - t, \lfloor (D-u)/s \rfloor)\right\} $$

where $V(B+1,0,0) = 1$ and $V(B+1,t,u) = 0$ otherwise. If $V(A,0,0) = 1$, you can achieve the goal by choosing $x_A$ so $V(A+1,x_1, A x_1) = 1$, then $x_2$ so $V(A+2, x_1 + x_2, A x_1 + (A+1) x_2) = 1$, etc.

Robert Israel
  • 448,999