0
$\begingroup$

This is straight from the book: Optimization Methods in Finance.

Overview

The question is about how the transition state works from the example provided in the book. I attempted to trace through it myself but came across a contradiction.

In Chapter 13, we come across an example similar to the Knapsack Problem. The main difference is we can make "multiple investments" in each project (instead of simple binary 1-0 choice)

The example problem

We want to optimize between 4 projects with total budget of $14 (values in millions)

$$ Maximize \;\; 11x_1 + 8x_2 + 6x_3 + 4x_4 \\ Subject \;to \;\; 7x_1 + 5x_2 + 4x_3 + 3x_4 <= 14 \\ x_j >= 0, \; j = 1..4$$

Note that $y_j$ will be the cost (constraint) and $p_j$ will be the profit (what we want to maximize) as we proceed.

The book proceeds to formulate the dynamic programming approach with four stages: $i=1,2,3,4$ where the fourth stage will have states $(4,0), (4,3), (4,6), (4,9), (4,12)$ corresponding to 0, 1, 2, 3, and 4 investments in the fourth project.

The decision to be made at stage $i$ is the number of times one invests in the investment opportunity $i$. Therefore, for state $(i,j)$, the decision set is given by:

$$ S(i,j) = \{d|\frac{j}{y_i} \geq d \} $$ where d is a non-negative integer

The transition state is : $$ T((i, j), d) = (i + 1, j - y_i* d) $$

My issue and contradiction

Now, let us say we have a state at stage 3: $(i,j)$ is $(3,12)$ Since investment 3 has a cost $y_3=4$, it means $(3,12)$ is a state where 4 investments are made in investment 3.

Calculating our decision set: $$S(3, 12) = \{d\|\frac{12}{4} \geq d\} \\S(3,12) = \{0, 1, 2, 3\}$$

However, since we are currently at \$12, that means we should only have \$2 left to spend.

Applying the transition function:

$$T(3,12), 0) = (4, 12 - 4*0)\\T(3,12), 0) = (4, 12)$$ How is this feasible? Also for the following:

$$T(3,12), 1) = (4, 12 - 4*1) \\T(3,12), 1) = (4,8)$$ This is a state that does not exist, since it was provided in the book that the possible states for stage 4 is $(4, 0), (4,3), (4,6), (4,9), (4,12)$

Pictures below for full problem:

KnapSack Problem

Decision Set and Transition

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.