Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and $v_l \in T$ of minimal cost $\sum_{i=1}^lf(v_i)$.

The length of the path has to be precisely $l$. However, an algorithm that finds the best solution for a path of length $1, 2, \ldots, l$ would be even better.

I use Simplex (Gurobipy, if you are curious) to solve this problem. I think my formulation can be improved, but I am looking for other approaches or known problems to which this can be reduced. I can provide more information about the size of $V, E, k,\ldots$ if needed.

I don't know if this falls more into the jurisdiction of stack overflow. In that case, I'll repost the question there.

Edit: In case you are curious, the original problem is about the Italian Dominating Number.

Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and $v_l \in T$ of minimal cost $\sum_{i=1}^lf(v_i)$.

The length of the path has to be precisely $l$. However, an algorithm that finds the best solution for a path of length $1, 2, \ldots, l$ would be even better.

I use Simplex (Gurobipy, if you are curious) to solve this problem. I think my formulation can be improved, but I am looking for other approaches or known problems to which this can be reduced. I can provide more information about the size of $V, E, k,\ldots$ if needed.

I don't know if this falls more into the jurisdiction of stack overflow. In that case, I'll repost the question there.

Edit: In case you are curious, the original problem is about the Italian Dominating Number.

Edit: The solution is in general not simple. Also, I'm looking for an optimal solution, not a heuristic.