3
$\begingroup$

Which algorithm would be suitable for finding or estimating the vector $$\mathbf{s}_{opt}=\begin{bmatrix} s_1 & \cdots & s_N \end{bmatrix}=\arg\max_{\mathbf{s}}\sum_{n=1}^{N}p_{s_n,n}$$ under the constraint $$\sum_{n=1}^{N}l_{s_n,n}\leq L_{max}$$ given known values for the integer $N$, the vector $\mathbf{p}_n=\begin{bmatrix} p_{1,n}\\ \vdots \\ p_{M_n,n} \end{bmatrix}$, the vector $\mathbf{l}_n=\begin{bmatrix} l_{1,n}\\ \vdots \\ l_{M_n,n} \end{bmatrix}$, the integer $L_{max}$ and all integers $M_n$?

Here are some restrictions showing that the size of the problem isn't very big: $$N\:\epsilon\:\mathbb{Z}\:|\:0<N<50$$ $$p\:\epsilon\:\mathbb{R}\:|\:0\leq p_{m,n}\leq 1\:|\:p_{1,n}=1\:|\:p_{M_n,n}=0$$ $$l\:\epsilon\:\mathbb{Z}\:|\:0\leq l_{m,n}\leq 30\:|\:l_{M_n,n}=0$$ $$M_n\:\epsilon\:\mathbb{Z}\:|\:2\leq M_n \leq 20$$

Another circumstance which may be of interest is that the problem will be solved repeatedly. In the first iteration $N=1$ and then for each iteration $N$ will increase as per the sequence $N=1,2,3,...$. The vectors $\mathbf{p}_n$ and $\mathbf{l}_n$, as well as the other inputs, will remain unchanged for all iterations $N=1,2,3,...$, meaning that the same problem just grows slightly step by step.

I am planning to implement this algorithm in JavaScript.

Edit: Real-world case

The mathematical optimization problem above has its origin in a real world (however, stupid) problem. Assume you need to communicate a text of $N$ words, but you have a limited total amount of characters to use, $L_{max}$. For each word $n$ you have found $M_n$ number of alternative representations (such as acronyms and synonyms) each with a probability of the reader to understand approximated to $p_{m,n}$. Now the goal is to choose which representation $s_n$ of each word should be chosen in order to maximize the probability of the receiver to understand the text. This probability can be approximated to the mean value all individual word probabilities.

$\endgroup$
  • 2
    $\begingroup$ What is the motivation behind this problem? It looks like some kind of knapsack, but trying to decipher abstract notation without knowing the intuition behind the problem is tiresome. It seems that a good way of solving this problem would be the classical (pseudopolynomial) approach of dynamic programming. You could index the subproblems with $n$ and the amount of slack left in the $L_{max}$ constraint. $\endgroup$ – Tom van der Zanden May 10 '15 at 20:44
  • $\begingroup$ @TomvanderZanden Expand to an answer? $\endgroup$ – Yuval Filmus May 11 '15 at 3:39
  • $\begingroup$ @TomvanderZanden Yes, it really looks like the knapsack problem! I was not aware of that one and it was exactly something like that I was looking for. Thanks! I will read more on that one in order to grasp the rest of your comment. My first reflection is that it is my problem has a little twerk. Instead of just chosing whether you should bring the item "apple", you need to choose which variant of the apple to bring. $\endgroup$ – nize May 11 '15 at 6:42
4
$\begingroup$

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<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,*)$.

$\endgroup$
  • $\begingroup$ I guess you are missing the summand $l_{j,i}$ in the constraint expression? I am sure the solution is what I am searching for, but I am actually not familiar with the basics of dynamic programming. Even after googling it, I don't really get it. Would you have any good proposal on where I should turn to figure out how I could implement the algorithm given the recurrence relation you have provided? Moreover, I tried to figure out the what the asterisk in the notation $D(*,r)$ represents, but without success. $\endgroup$ – nize May 11 '15 at 17:41
  • $\begingroup$ Maybe the wikipedia article on knapsack/dp? The $*$ isn't all that common notation, I'm using it as a wildcard, saying "for all values that the argument could take". So $D(x,r)$ is $-\infty$ if $r<0$ and $D(x,r)=0$ if $x=N+1$. $\endgroup$ – Tom van der Zanden May 11 '15 at 19:01
  • $\begingroup$ You state I am after $D(N,L_{max})$. Inserting these arguments in the recurrence relation gives $\max_{s_N\epsilon \{2,...,M_N\}}p_{s_N,N}+D(N+1,L_{max}-l_{s_N,N})=\max_{s_N\epsilon \{2,...,M_N\}}p_{s_N,N}$ since $D(N+1,*)=0$. Then you wouldn't need to compute $D(n,r)$ for any $n\neq N$? What am I getting wrong? $\endgroup$ – nize May 11 '15 at 19:58
  • $\begingroup$ The value you actually want is $D(0,L_{max})$. The recurrence relation is backwards from what it would usually be to accommodate your growing input requirement, hence my mistake. $\endgroup$ – Tom van der Zanden May 11 '15 at 21:08
  • $\begingroup$ Ok, then I'm missing another pedagogical step... Inserting the argument $n=0$ in the definition given in the beginning of the second paragraph I get $max_\mathbf{s}\sum_{i=1}^0 p_{s_i,i} \equiv 0$. $\endgroup$ – nize May 12 '15 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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