# Linear programming approach to dynamic programming - an initial pair of state-decisions

I aim to solve the following Bellman equation:

$$$$v(\vec{s}) = \min_{\vec{x} \in \Xi_{\vec{s}}} \big\{c(\vec{s}, \vec{x}) + \lambda \times \sum_{\vec{s}^{'}\in S} p(\vec{s}^{'} | \vec{s}, \vec{x}) \times v(\vec{s}^{'})\big\} \hspace{2cm} \forall \vec{s} \in S$$$$

I use the linear programming approach to solve the above equation like below:

Model 1: $$$$\max \Big\{\sum_{\vec{s} \in S} \eta(\vec{s}) \times v(\vec{s})\Big\}$$$$ subjected to: $$$$c(\vec{s}, \vec{x}) + \lambda \times \sum_{\vec{s}^{'} \in S} p(\vec{s}^{'} | \vec{s}, \vec{x}) \times v(\vec{s}^{'}) \ge v(\vec{s}) \hspace{1cm} \forall \vec{s} \in S; \vec{x} \in \Xi_{\vec{s}}$$$$ $$$$v(\vec{s}) \in \mathbb{R}_{\geq0}$$$$

Due to the curse of dimensionality, I use a basis function to approximate the value function and solve the dual of the above problem using a column generation (further detail can be found here: 10.1016/j.ejor.2012.06.046). The column generation algorithm includes a master problem and a subproblem like below:

Model 2, Master problem: where the algorithm iteratively solves the dual problem - the shadow prices of constraints are equal to optimal approximation coefficients.

$$$$\min \sum_{\vec{s} \in S} \sum_{\vec{x} \in \Xi_{\vec{s}}} c(\vec{s}, \vec{x}) \times \chi(\vec{s}, \vec{x})$$$$

subjected to:

$$$$(1 - \lambda) \times \sum_{\vec{s} \in S} \sum_{\vec{x} \in \Xi_{\vec{s}}} \chi(\vec{s}, \vec{x}) = 1$$$$ $$$$\sum_{\vec{s} \in S} \sum_{\vec{x} \in \Xi_{\vec{s}}} \mu_{koi}(\vec{s}, \vec{x}) \times \chi(\vec{s}, \vec{x}) \geq \mathbb{E}_{\eta} [p^w_{koi}] \hspace{1cm} \forall k \in \mathcal{K}; o \in \mathcal{O}; i \in \mathcal{I}$$$$ $$$$\sum_{\vec{s} \in S} \sum_{\vec{x} \in \Xi_{\vec{s}}} \delta_{kti}(\vec{s}, \vec{x}) \times \chi(\vec{s}, \vec{x}) \geq \mathbb{E}_{\eta} [p^m_{kti}] \hspace{1cm} \forall k \in \mathcal{K}; t \in \mathcal{T}; i \in \mathcal{I}$$$$ $$$$\chi(\vec{s}, \vec{x}) \in \mathbb{R}_{\geq0}$$$$

Model 3, Sub-problem: where the algorithm finds feasible state-decision pairs to be added to the master problem. $$$$\max \Big\{(1 - \lambda) \times V^0 + \sum_{k \in \mathcal{K}} \sum_{o \in \mathcal{O}} \sum_{i \in \mathcal{I}} V^w_{koi} \times \mu_{koi}(\vec{s}, \vec{x}) + \sum_{k \in \mathcal{K}} \sum_{t \in \mathcal{T}} \sum_{i \in \mathcal{I}} V^m_{kti} \times \delta_{kti}(\vec{s}, \vec{x}) - c(\vec{s}, \vec{x})\Big\}$$$$

subjected to:

$$$$\sum_{p \in \mathcal{P}^w} \sum_{j \in \mathcal{J}} \sum_{t \in \mathcal{T}} \sum_{\substack{b \in \mathcal{B}_c \\ c \in \mathcal{C}}} z_{pjtib} \times R^1_{pk} \times R^1_{po} \leq p^w_{koi} \hspace{1cm} \forall k \in \mathcal{K}; o \in \mathcal{O}; i \in \mathcal{I}$$$$ $$$$\sum_{p \in \mathcal{P}^m} \sum_{j \in \mathcal{J}} \sum_{\substack{b \in \mathcal{B}_c \\ c \in \mathcal{C}}} z_{pjtib} \times R^1_{pk} = p^m_{kti} \hspace{1cm} \forall k \in \mathcal{K}; t \in \mathcal{T}; i \in \mathcal{I}$$$$ $$$$(\vec{s}, \vec{x}) \in S \times \Xi_{\vec{s}}$$$$

My problem starts from here! To initiate the column generation algorithm, I need to have at least one feasible pair of state-decision for Model 2. As suggested by Saure et al. (2012), I iteratively solve Models 4 and 3 until the objective function of Model 4 becomes equal to zero (meaning that a set of feasible state-decisions is found for Model 2 so I can start the column generation). Starting from an initial hypothesized state, I solve Model 4, finds the shadow prices of constraints and update $$V^0$$, $$V^w_{koi}$$ and $$V^m_{kti}$$, and solve Model 3 (to update $$P$$ for Model 4). Solving Models 4 and 3 for a few iterations, the objective of Model 4 improves for a while. However, Model 3 stops providing new outcomes for decision variables (generates an identical solution).

What would be the reason for this issue?

Let me know if you need further information.

Model 4:

$$$$\min \Big\{U^0 + \sum_{k \in \mathcal{K}} \sum_{o \in \mathcal{O}} \sum_{i \in \mathcal{I}} U^w_{koi} + \sum_{k \in \mathcal{K}} \sum_{t \in \mathcal{T}} \sum_{i \in \mathcal{I}} U^m_{kti}\Big\}$$$$

Subjected to:

$$$$(1 - \lambda) \times \sum_{\vec{s} \in P} \sum_{\vec{x} \in \Xi_{\vec{s}}} \chi(\vec{s}, \vec{x}) + U^0 = 1$$$$ $$$$\sum_{\vec{s} \in P} \sum_{\vec{x} \in \Xi_{\vec{s}}} \mu_{koi}(\vec{s}, \vec{x}) \times \chi(\vec{s}, \vec{x}) + U^w_{koi} \geq \mathbb{E}_{\eta} [p^w_{koi}] \hspace{1cm} \forall k \in \mathcal{K}; o \in \mathcal{O}; i \in \mathcal{I}$$$$ $$$$\sum_{\vec{s} \in P} \sum_{\vec{x} \in \Xi_{\vec{s}}} \delta_{kti}(\vec{s}, \vec{x}) \times \chi(\vec{s}, \vec{x}) + U^m_{kti} \geq \mathbb{E}_{\eta} [p^m_{kti}] \hspace{1cm} \forall k \in \mathcal{K}; t \in \mathcal{T}; i \in \mathcal{I}$$$$ $$$$U^0, U^w_{koi}, U^m_{kti} \in \mathbb{R}_{\geq0}$$$$