Which optimization algorithm would you recommend for this small multidimensional problem?
This problem is effectively knapsack, where the size of the knapsack is $L_{max}$. The items are $1,\ldots,n$, and for each item $i$ we can select a quantity (to include in our knapsack) of $j\in\{2,\ldots,M_n\}$. Taking quantity $j$ of item $i$ gives reward $p_{j,i}$ and takes up $l_{j,i}$ space in the knapsack.

Let $D(n,r)$ be $max_s \sum_{i=1}^{n} p_{s_i,i}$ under the constraint that $\sum_{i=1}^{n} l_{j,i} \leq r$. $D(N,L_{max})$ (which is the value you're after) can be computed in $O(L_{max}\cdot NM)$ time (where $M$ is $max_i M_i$) using dynamic programming.

Effectively $D(n,r)$ represents the best way (mean probability) to represent the first $n$ words using at most $r$ space. The best way to represent $D(n,r)$ is to combine some choice of representing word $n$ with the best way to represent the remaining $n-1$ words in however many characters are left. This is expressed by the recurrence relation:

$$D(n,r)=max_{s_n\in\{2,\ldots,M_n\}} p_{s_n,n} + D(n-1,r-l_{s_n,n})$$

Where $D(*,r)=-\infty$ if $r&lt;0$ and $D(0,*)=0$.

What is very important is that you store (and reuse) the intermediate values of $D(n,r)$ during the computation, as this will save significantly on computation time. Reusing these values will also allow you to deal with the growing input requirement, since the values encountered when computing $D(n,*)$ can be reused when computing $D(n+1,*)$.