# Optimizing through a Transition matrix, in a non-stepwise manner

I made some sort of a transition matrix of an increase in probability of success, given the allocation of some finite resource (e.g. 4 in this case). At this moment, I consider the allocation in a stepwise manner. That is, for every +1 increase, I just check which choice maximizes. Generally, the more I add to one option, the lower the increase will become (thus opening the window for other choices).

However, I noticed that sometimes it gets stuck: if only I'd be willing to allow for 0 increase for sometime, I could get an amazing increase.

How can I maximize the increase by not just looking in a stepwise fashion, but considering it as a whole?

            inc1     inc2      inc3      inc4

option1    0.0000   0.0000    0.3021    0.1541
option2    0.1000   0.0100    0.0010    0.0001
option3    0.2      0.0000    0.0000    0.0000


Note that stepwise would go like this:

     option3 -> option2 -> option2 -> option2 = 0.311


whereas the optimal solution here is:

     option3 -> option1 -> option1 -> option1 = 0.5021


Also note that this is a simple case and there are more options and different payouts. Therefore, answers just considering this specific problem, and which do not generalize, are useless.

What would be your approach to this problem?

• I am not really sure for appropriate tags, so feel free to edit. – PascalVKooten Apr 22 '14 at 8:00
• I think it will be a problem with perhaps 20 options and the total sum might be 25. I'm looking for an efficient implementation, or just some general tricks not to have to consider every single combination – PascalVKooten Apr 24 '14 at 12:11
• This seems like an algorithmic question and would get more exposure and possible ideas if it were moved over to SO? – Hao Ye Apr 25 '14 at 18:25
• @HaoYe I realized it before, and I completely agree. It's just that I cannot migrate it myself, or can I? – PascalVKooten Apr 25 '14 at 18:32
• Besides SO, either cs.stackexchange.com or scicomp.stackexchange.com might have been relevant. The possible connection to Markov chains does not seem very relevant in terms of solving the problem. However, see my just-posted answer for some solution ideas. – Juho Kokkala Apr 26 '14 at 14:26

Just to summarize and add a bit of formalism, you want to maximize a payout

$P(x,y,z) = f(x) + g(y) + h(z)$

where $f,g,h$ are payouts for each option, and $x,y,z$ are integers and sum to 4. The matrix you provided is the derivative (increases) of the payout for each option.

For example, $g(y) = \sum_1^y 10^{-y}$.

If all three $f,g,h$ were concave functions, then the greedy strategy works fine. However, in some of your cases, one of the options isn't concave; it goes from zero, then up, then slows down again, and greedy search is suboptimal.

Anyway, your specific example is small, so an exhaustive search is easy. In general, this sounds like an integer programming problem, with a linear constraint and nonlinear objective. IIRC, that is an NP-hard problem, but there's off the shelf software that will do a pretty good job.

• OP can you verify that this formalization of the problem is what you actually want to solve? – Bitwise Apr 22 '14 at 16:54
• @Bitwise Yes. I believe that the problem will be small enough that an exhaustive search would in fact be okay for my application, but I'm still a bit lost on how to approach it. I think it will be a problem with perhaps 20 options and the total sum might be 25. – PascalVKooten Apr 22 '14 at 17:52
• @NealFultz That indeed seems like a perfect summary. – PascalVKooten Apr 22 '14 at 18:51
• What might the complexity be for this problem, perhaps some pruning is needed? – PascalVKooten Apr 22 '14 at 23:12

I am assuming the formulation from Neal Fultz's answer. I can think of two approaches: binary linear integer programming (hinted at Neal's answer), or dynamic optimization. Based on my quick testing with MATLAB, at least with a randomly generated increment matrix, $N_o=20$ options and $N_n=25$ increments, the dynamic optimization approach seems faster (answer produced in 0.006 seconds with the computer I'm currently using and perhaps rather unoptimized code).

## Dynamic Programming

Note that the optimal selections for options $j,\ldots,N_o$ depend only on the number of increments remaining after making selections for options $1,\ldots,j-1$. Hence, the problem follows the optimality principle, and dynamic programming may be used. Start from the last iteration, and compute the optimal policy as a function of remaining increments (taking into account the remaining increments for next step), and iterate this backwards. For the last option, obviously all increments are used.

To work out your example case:

1. For the last (3rd) option, all increments are used, and the score as a function of $(0,\ldots,4)$ increments remaining at this step is $(0,0.2,0.2,0.2,0.2,0.2)$.
2. 2nd option: If there are no increments remaining, score is 0. If 1 increment, it is better to not use it (score 0.2). If 2 increments, one is used, one left for next round (score 0.3). If 3 increments, two used, one left for next rounds (score 0.311). If 4 increments, 3 used, one left for next rounds (score 0.3111). Thus, at this round, the score of remaining rounds is $(0,0.2,0.3,0.311,0.311)$.
3. 1st option: For the first option, we need to only look at the 4 increments remaining -case. The best option is to use 3 increments here, with 1 remaining and score $0.3021+0.2 = 0.5021$.

The optimal strategy can be found by working forward, counting the number of remaining increments and recalling the optimal pick for that remaining number of increments.

## Zero-one Integer Programming

Let $x_{ij}$ be a binary variable indicating whether we select the $j$th increment of $i$th option. The optimization problem is $$\max_x \sum_i^{N_o} \sum_j^{N_i} c_{ij}x_{ij},$$ where $c_{ij}$s are the numbers in your increment table as in the question. We have two types of constraints. First, each increment can be picked only if the previous increment is picked with the same option: $$\forall i\in\{1,\dots,N_o\}, \forall j\in\{2,\ldots,N_i\}: x_{ij}\leq x_{i\,j-1}.$$ The second type of constraint is that the we cannot overall select more than $N_i$ increments, $$\sum_{i=1}^{N_o} \sum_{j=1}^{N_i} x_{ij} \leq N_i.$$ Both the objective function and the constraints are linear, wherefore this is a zero-one integer programming problem, for which solution algorithms are implemented in optimization software packages (Branch\&Cut + Simplex for the LP subproblems is one idea I know of). However, at least with MATLABs bintprog, this was slower than the dynamic programming approach with $N_i=25,N_o=20$. However, it is sometimes possible to speed up integer programming problems by improving the problem formulation, the one I presented here is perhaps not optimal, I don't know.