patternMinor
Optimization problem where penalty is sensitive to permutation
Viewed 0 times
problempenaltywhereoptimizationpermutationsensitive
Problem
Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I want to minimize my penalty P. There is no limit to the amount of values I use (I could do 4x5, 20x1 and any other possibility).
The penalty is not based on the amount of values I use, but instead on the intermediate values of the summation.
In this example, let's assume the penalties are as follows:
where k is the current value being added to my intermediate sum S.
So if I consider e.g. [1,2,3,4,5,5] (in that particular order), my total penalty would be P=11+12+23+34+35+45=56.
However, the penalty changes if I permute my array to e.g. [1,5,4,5,2,3] (P=53) or [2,4,5,1,3,5] (P=61).
In this simple example, we have 192 different sets of values that can together add up to 20. The number of possible permutations per set (taking into account non-unique values) varies between 1 (in case of 20x1, 10x2 etc) and 15840 (7x1, 3x2, 1x3, 1x4). The naive approach would be to just loop through all sets and their permutations, which is doable for the given example.
However, my actual problem has about 2000 possible sets of numbers and the number of permutations goes all the way up to ~1E+8. It is no longer fun to use a naive approach in this case.
I do know that I can greatly reduce my number of permutations, as the order of my values does not matter if I stay within the same range (when I'm at S=11, it no longer matters in what way I add the final 9).
My question is how I can properly implement this knowledge to improve my naive algorithm such that it disregards those permutations a priori (first generating all permutations and then removing is not really an option, as even 8-bit unsigned integers will generate 15 GB arrays for all permutations). Furthermore, I was wondering whether there are any additiona
The penalty is not based on the amount of values I use, but instead on the intermediate values of the summation.
In this example, let's assume the penalties are as follows:
- 1 * k for 0
- 2 * k for 2
- 3 * k for 6
- 4 * k for 11
where k is the current value being added to my intermediate sum S.
So if I consider e.g. [1,2,3,4,5,5] (in that particular order), my total penalty would be P=11+12+23+34+35+45=56.
However, the penalty changes if I permute my array to e.g. [1,5,4,5,2,3] (P=53) or [2,4,5,1,3,5] (P=61).
In this simple example, we have 192 different sets of values that can together add up to 20. The number of possible permutations per set (taking into account non-unique values) varies between 1 (in case of 20x1, 10x2 etc) and 15840 (7x1, 3x2, 1x3, 1x4). The naive approach would be to just loop through all sets and their permutations, which is doable for the given example.
However, my actual problem has about 2000 possible sets of numbers and the number of permutations goes all the way up to ~1E+8. It is no longer fun to use a naive approach in this case.
I do know that I can greatly reduce my number of permutations, as the order of my values does not matter if I stay within the same range (when I'm at S=11, it no longer matters in what way I add the final 9).
My question is how I can properly implement this knowledge to improve my naive algorithm such that it disregards those permutations a priori (first generating all permutations and then removing is not really an option, as even 8-bit unsigned integers will generate 15 GB arrays for all permutations). Furthermore, I was wondering whether there are any additiona
Solution
I will outline two different solution methods. Either one will work -- pick whichever one you find easiest to understand and implement.
Dynamic programming
This can be solved using dynamic programming. We'll fill in a one-dimensional table, so that $T[s]$ stores the penalty of the best (lowest-penalty) way to obtain a sum of exactly $s$. Once we've filled in all of the entries, $T[20]$ will tell you the lowest penalty achievable for any combination that sums to 20.
So how do we fill in the table entries? We can fill them in recursively:
$$T[s] = \min(T[s-1]+p(s-1,1), T[s-2]+p(s-2,2), \dots, T[s-5]+p(s-5,5))$$
where $p(s,k)$ is the penalty for adding the number $k$ when the intermediate sum is $s$. In the question, you tell us that $p(s,k) = k$ for $0 \le s < 2$, $p(s,k) = 2k$ for $2 \le s < 6$, etc.
Also, we have the base cases $T[0] = 0$. As a convention, we'll agree that $T[-1]=T[-2]=T[-3]=T[-4]=\infty$. Then you can fill in $T[1],T[2],\dots,T[20]$ in that order, using the recursive formula above.
This will give you the penalty of the best way to achieve the sum $20$. If you also want to output the specific combination that achieves that penalty, you can keep track of that with a small modification. Basically, each time you fill in a $T[i]$ entry with some penalty value, on the side keep track of the combination that led to that penalty value.
Graph search
Construct a weighted directed graph, with vertices 0, 1, 2, .., 20. Each vertex corresponds to a possible intermediate sum. From each vertex (intermediate sum) $s$, add five outgoing edges, corresponding to the five possibilities for the number you add. The length of the edge from $s$ to $s+i$ (for $i=1,2,\dots,5$) is the penalty for adding $i$ to an intermediate sum $s$, according to the rules described in your question.
Now find the shortest path from vertex 0 to vertex 20 in this graph. That path will correspond to a combination of values that sum to 20, and the total length of that path will correspond to the penalty of that path. The shortest path will correspond to the combination with lowest penalty. You can use any standard algorithm for computing shortest paths in a graph, such as Dijkstra's algorithm.
Dynamic programming
This can be solved using dynamic programming. We'll fill in a one-dimensional table, so that $T[s]$ stores the penalty of the best (lowest-penalty) way to obtain a sum of exactly $s$. Once we've filled in all of the entries, $T[20]$ will tell you the lowest penalty achievable for any combination that sums to 20.
So how do we fill in the table entries? We can fill them in recursively:
$$T[s] = \min(T[s-1]+p(s-1,1), T[s-2]+p(s-2,2), \dots, T[s-5]+p(s-5,5))$$
where $p(s,k)$ is the penalty for adding the number $k$ when the intermediate sum is $s$. In the question, you tell us that $p(s,k) = k$ for $0 \le s < 2$, $p(s,k) = 2k$ for $2 \le s < 6$, etc.
Also, we have the base cases $T[0] = 0$. As a convention, we'll agree that $T[-1]=T[-2]=T[-3]=T[-4]=\infty$. Then you can fill in $T[1],T[2],\dots,T[20]$ in that order, using the recursive formula above.
This will give you the penalty of the best way to achieve the sum $20$. If you also want to output the specific combination that achieves that penalty, you can keep track of that with a small modification. Basically, each time you fill in a $T[i]$ entry with some penalty value, on the side keep track of the combination that led to that penalty value.
Graph search
Construct a weighted directed graph, with vertices 0, 1, 2, .., 20. Each vertex corresponds to a possible intermediate sum. From each vertex (intermediate sum) $s$, add five outgoing edges, corresponding to the five possibilities for the number you add. The length of the edge from $s$ to $s+i$ (for $i=1,2,\dots,5$) is the penalty for adding $i$ to an intermediate sum $s$, according to the rules described in your question.
Now find the shortest path from vertex 0 to vertex 20 in this graph. That path will correspond to a combination of values that sum to 20, and the total length of that path will correspond to the penalty of that path. The shortest path will correspond to the combination with lowest penalty. You can use any standard algorithm for computing shortest paths in a graph, such as Dijkstra's algorithm.
Context
StackExchange Computer Science Q#71053, answer score: 2
Revisions (0)
No revisions yet.