0
$\begingroup$

Consider the following model: \begin{align*} max \quad Z &= 19x_1 - 3x_1^2 + 5x_2^2 - x_2^4 + 4x_3 \\ & s.t. \quad x_1 + 3x_2 + 3x_3 \leq 7 \\ & \quad \quad \quad x_1,x_2,x_3 \geq 0 \end{align*}

Also note that all $x_i$ are integers. How does one formulate a Bellman equation for each stage? Can someone maybe give me a hint so I learn from it.

$\endgroup$

2 Answers 2

4
$\begingroup$

Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$. Let $a_i$ be the constraint coefficient of $x_i$, and let $z_i(x_i)$ be the contribution to the objective value for variable $x_i$. For example, $z_2(x_2) = 5x_2^2-x_2^4$. The boundary condition is $f(0,b)=0$. To derive the Bellman equation as a recurrence for $f(n,b)$ in terms of $f(n-1,.)$, condition on the finite number of choices for the value of $x_n$: $$f(n,b) = \max_{x_n \in \{0,\dots,\lfloor b/a_n \rfloor\}} (z_n(x_n) + f(n-1,b-a_n x_n))$$ The resulting values of $f$ are as follows: \begin{matrix} n\backslash b &0 &1 &2 &3 &4 &5 &6 &7 \\ \hline 0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 1 &0 &16 &26 &30 &30 &30 &30 &30 \\ 2 &0 &16 &26 &30 &30 &30 &34 &34 \\ 3 &0 &16 &26 &30 &30 &30 &34 &\color{red}{34} \\ \end{matrix}

$\endgroup$
2
$\begingroup$

Assuming there are n stages, S symbolized by say $s$ define $x$ as $x_{1,s},x_{2,s}, x_{3,s}$: decision vector $X_s$ and $Z(X_s)$ as optimal value for every stage $s$ subject to same constraint
Using Bellman equation its
Z = max[$Z(X_{s_O}) + \sum_{i=1}^n Z(X_{s+i}:b^{T} X_{s+i} \le 7)]$ $\forall s \in\ $S
s.t.
$b^T X_{s_0} \le 7$

I would however solve it like: max $Z(X_{s}) \ \forall s \in\ $ S
s.t.
$b^T X_{s} \le 7$
$L_{s+1} \le max(Z(X_{s+1}:b^{T} X_{s+1} \le 7)$

Since now $X$ is integer and vector of $x_i$ where $i$ is stage [1,2,3] so we have finite set
For stage=3, $x_3$ can have values of [0,1,2]
$\begin{array}{c|c|c|} & \text{$x_3$} & \text{$Z=4x_3$} & \text{Max} \\ \hline \text{State 1} & 0 & 0 & 0 \\ \hline \text{State 2} & 1 & 4 & 4 \\\hline \text{State 3} & 2 & 8 & 8 \\ \hline \end{array}$
$Max(stage=3)=8$ at $x_3=2$

For stage 2, $x_2$ can have values of [0,1,2] with rhs of constraint=7
$\begin{array}{c|c|c|} & \text{$x_2$} & \text{$x_3$} & \text{rhs=7} & \text{$Z=5x_2^2 - x_2^4 +max(Stage 3 \ Z \ for \ x_3$} & \text{Max}\\ \hline \text{Row 1} & 0 & 0 & 7 & 0 & \\ \hline \text{Row 2} & 0 & 1 & 7-3(1)=4 & 4 & \\ \hline \text{Row 3} & 0 & 2 & 1 & 8 & 8 \\ \hline \text{Row 4} & 1 & 0 & 4 & 4 & \\ \hline \text{Row 5} & 1 & 1 & 1 & 8 & 8 \\ \hline \text{Row 5} & 2 & 0 & 1 & 4 & 4 \\ \hline \end{array}$
$Max(stage=2)=8$ at either $(0,2)$ or $(1,1)$. Cant consider (1,2) or (2,1) as this will violate constraint.\

For stage 1, $x_1$ can have values of [0,1,2]
$\begin{array}{c|c|c|} & \text{$x_1$} & \text{$x_2$} & \text{rhs=7} & \text{$Z=19x_1 - 3x_1^2 + max (Stage2 \ Z \ for \ x_2)$} & \text{Max}\\ \hline \text{Row 1} & 0 & 0 & 7 & 8 \\ \hline \text{Row 2} & 0 & 1 & 7-3(1)=4 & 8 \\ \hline \text{Row 3} & 0 & 2 & 1 & 4 & 8 \\ \hline \text{Row 4} & 1 & 0 & 6 & 24 \\ \hline \text{Row 5} & 1 & 1 & 3 & 24 \\ \hline \text{Row 5} & 1 & 2 & 0 & 20 & 24 \\ \hline \text{Row 5} & 2 & 0 & 5 & 34 \\ \hline \text{Row 5} & 2 & 1 & 2 & 34 & 34 \\ \hline \text{Row 6} & 3 & 1 & 1 & 34 & 34 \\ \hline \end{array}$
$x_1 \ge 4$ onwards objective val will start declining

So at Stage 1, Z = 34 for $X = [3,1,0], [2,1,2]$

$\endgroup$
2
  • $\begingroup$ Could you maybe give me a bellmann equation with the variables and obj function of my problem, I do no really understand this formulation perfectly. $\endgroup$ Dec 16, 2022 at 9:31
  • 1
    $\begingroup$ Just corrected myself $\endgroup$ Dec 16, 2022 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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