Optimization problem where penalty is sensitive to permutation

Question

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:

• 1 * k for 0 <= S < 2
• 2 * k for 2 <= S < 6
• 3 * k for 6 <= S < 11
• 4 * k for 11 <= S < 20

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=1*1+1*2+2*3+3*4+3*5+4*5=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 additional improvements that could be made here.

Answer 1

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.

Answer 2

Another way to view the problem using Dynamic Programming might be the following. We can first define the discrete recurrence relation of your sequence to be the following:

\begin{align} s_{n+1} &= s_{n} + u_{n} \end{align}

where $s_{n}$ is the sum up to, but not including, the $n^{th}$ term of the sequence, and $u_{n}$ is the $n^{th}$ sequence term you will choose based on your set of possible sequence term values. Note all the possible values for the variables are as followed (based on your example):

\begin{align} u_{n} &\in \mathcal{U} = \lbrace 1,2,3,4,5\rbrace \;\; \forall n\\ s_{n} &\in \mathcal{S}_{n} =\lbrace k \in \mathbb{N}: (n-1) \leq k \leq 5(n-1) \rbrace \end{align}

The above expression shows the set of possible values for $s_1$ is only $\lbrace 0 \rbrace$, but grows larger each step in the sequence. The possible values for $s_{n}$ can be reduced by tailoring the sets for a sum equal to $20$, but you can figure that out on your own. The next step is to define some cost function we wish to minimize with respect to $\lbrace u_{n} \rbrace_{n=1}^{M}$, perhaps:

\begin{align} V &= \gamma (s_{M+1}-20)^2 + \sum_{n=1}^{M} P_{n}(s_{n},u_{n}) \end{align}

where $M$ is the size of the sequence, $s_{M+1}$ is the final sum across all values chosen in the sequence, $\gamma$ is some constant, and $P_{n}(\cdot,\cdot)$ is some penalty at the $n^{th}$ sequence as a function of the current sum ($s_{n}$) and $n^{th}$ chosen sequence term value ($u_{n}$). We can break this into pieces and recursively solve the optimization by doing the following:

\begin{align} V^{*}_{M+1}(s) &= \gamma (s - 20)^2 \; \forall s \in \mathcal{S}_{M+1} \\ V^{*}_{n}(s) &= \min_{u \in \mathcal{U}} P_{n}(s,u) + V^{*}_{n+1}(s+u) \;\;\forall s \in \mathcal{S}_n\\ u^{*}_{n}(s) &= \arg \min_{u \in \mathcal{U}} P_{n}(s,u) + V^{*}_{n+1}(s+u) \;\; \forall s \in \mathcal{S}_n \end{align}

Since this problem is discrete, you can obtain $V^{*}_{n}(s),u^{*}_{n}(s)$ by just looping through all $u \in \mathcal{U}$ for some $s \in \mathcal{S}_{n}$ and store the best cost and choice values as $V^{*}_{n}(s),u^{*}_{n}(s)$ in lookup-tables/arrays. Once you have computed those optimal values, you can start at $s_1 = 0$ and generate an optimal sequence using the discrete recurrence relation and $u^{*}_{n}(s)$.

Edit 3/5/2017

I implemented a code for the vanilla approach I describe above that you can check out here. Using this code, you can specify the sequence size you're interested in, the range of values that make up $\mathcal{U}$, the function $P_{n}(s_n,u_n)$, and the final cost term (which I define as $\gamma (s - 20)^2$ ). The algorithm technically obtains an optimal policy (that need not be unique) and then uses it to generate the optimal sequence.

Using the example provided by the OP, the code finds a sequence of $( 1, 4, 5, 5, 1, 4 )$ as optimal with a penalty of $P = 50$. If I then increase the sequence size to have 10 elements, the optimal sequence $( 1, 3, 1, 5, 5, 1, 1, 1, 1, 1 )$ comes out with a penalty of $P = 51$. If I increase the sequence size to have 15 elements, the optimal sequence $( 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 1, 1, 1, 1, 1 )$ comes out with a penalty of $P = 56$.

The Dynamic Programming formulation makes these results quite efficient to obtain, though things could be slimmed down further with some clever modifications.

Answer 3

With the help of D.W.'s answer I managed to tackle the problem quite easily.

See below code for my implementation of the example problem in MATLAB using dynamic programming. If there's any way to further optimize this, I'd love to hear it!

edit: also added the graph search approach. That one was ridiculously simple to implement..!

Caller script (Dynamic programming)

% Set target value
V = 20;

% Define globals for lookup-table LUT and allowed values pVals
global pVals LUT
pVals   = randperm(5);  % use values 1 to 5 in random order
LUT     = cell(2,V);    % row 1: minimum penalty | row 2: used values

% Perform the calculation
[minPenal, usedVals] = T(V);

% Verify correctness of answer
currPenal = 0;
currSum   = 0;
for ii=1:length(usedVals)
    currPenal = currPenal + p(currSum, usedVals(ii));
    currSum   = currSum + usedVals(ii);
end

if isequal(minPenal, currPenal) && (currSum==V)
    fprintf('\rPossible solution (P = %d):\n%s\n', minPenal, num2str(usedVals))
else
    fprintf('\rSomehow the recursion failed to obtain a solution... :(\n')
end

The recursive function (Dynamic programming)

function [minPenalUpToVal, bestSeq] = T(targetVal)

global pVals LUT

if ~isempty(LUT{1,targetVal})
    % No need to redo the calculation if it has been done already
    minPenalUpToVal = LUT{1,targetVal};
    bestSeq         = LUT{2,targetVal};

else
    % Initialize arrays    
    currPenal   = zeros(1,length(pVals));
    currSeq     = cell(1,length(pVals));

    % Loop over all possibile "previous states" that could result in V
    for pv = 1:length(currPenal)

        % Fetch the increment that may have made the current target possible
        incr = pVals(pv);

        if (targetVal-incr < 0) % Invalid, we rule this out by setting the penalty to inf
            currPenal(pv)  = inf;

        elseif (targetVal-incr == 0) % We know the penalty is zero at zero, so we don't need a minimum penalty
            currPenal(pv)  = 0 + p(targetVal-incr,incr);

        else % Recursive approach to get the minimum penalty up to V along with a possible solution to get there
            [penalUpToVal, currSeq{pv}] = T(targetVal-incr);
            currPenal(pv)               = penalUpToVal + p(targetVal-incr,incr);
        end
    end

    % We are only interested in the lowest penalty to get to V
    [minPenalUpToVal, idx]  = min( currPenal );
    bestSeq                 = [currSeq{idx} pVals(idx)];

    % Store these above quantities in our lookup-table
    LUT{1,targetVal} = minPenalUpToVal;
    LUT{2,targetVal} = bestSeq;

end

end

Caller script (Graph search)

% Set target value
V       = 20;
pVals   = randperm(5);  % use values 1 to 5 in random order

% Preallocate matrix
A = zeros(V+1,V+1);
for ii=1:V+1 % Loop over nodes
    for jj=pVals % Generate the edges
        if (ii+jj <= V+1) % Avoid exceeding our target
            A(ii, ii+jj) = p(ii-1, jj);
        end
    end
end

% Solve the problem with MATLAB built-in functions.
G       = digraph(A);
[sP,dP] = shortestpath(G, 1, V+1);
fprintf('\rPossible solution (P = %d):\n%s\n', dP, num2str(diff(sP)));

Penalty function

function p_out = p(s, k)

if (s < 2)
    p_out = 1*k;

elseif (s < 6)
    p_out = 2*k;

elseif (s < 11)
    p_out = 3*k;

elseif (s < 20)
    p_out = 4*k;

end

end

Answer 4

I'd change it from "penalties" to rewards. Pretend you have n slots that you need to fill with coins, and you have piles with different amounts of coins available. You can take a pile of k coins, find k consecutive empty slots, and fill these slots with coins.

Now the rewards: In your example, if you take a pile of k points and start dropping them at position 0 ≤ S < 2, and S + k > 2, then you get S + k - 2 rewards. If you start dropping them at position 2 ≤ S < 6, and S + k > 6, then you get S + k - 2 rewards and so on.

We can simplify this: If you drop m coins at position S, and S is the highest position 0 ≤ S < 2 where coins are dropped, then you get S + k - 2 rewards. In your example you can get 3 rewards (the fourth reward is always zero), so you maximise the sum of those three rewards.