# Resources¶

The core of handling constraints in networks using the dynamic programming algorithm is using the notion of accumulating resources and verify bounds while traversing the graph.

In the dynamic programming algorithm labels represent state and a resource is an element in the state. The cost component of a label can be considered as an unbounded resource and hence results in a state element.

Resource Order

Adding resource in the right order may have a significant impact on performance. For the purpose of extending, checking feasibility and dominance, resources states are checked in the order they are added (cost first). Quick rejections are done if a check fails, hence it is usually preferred to add the most constraining resources first.

First Resource

The first resources added should have a non-decreasing resource extension function to guarantee performance. Furthermore, for the first resource there must not exist a cycle in the graph with zero consumption for that resource.

Direction

The dynamic programming algorithm is a mono-directional algorithm. Hence, only forward extensions are support for now.

## Resource Extension Functions¶

A resource extension function (REF) defines how resources are extended along an edge in the graph. In principal a REF can take any form, however for performance reasons it makes sense to have simple expressions and preferable non-decreasing functions.

In general a REF for a resource $r$ when extending that resource from $i$ to $j$ can be described as

$S_{r,j} = f_{r,ij}(S_{r,i})$

Resource bounds are defined in the interval $[l_{r,i}, u_{r,i}]$ for each vertex (or edge), and an extension is feasible if $S_{r,i} \in [l_{r,i}, u_{r,i}]$.

## Dominance¶

In the dynamic programming algorithm a dominance check is performed between two labels $L$ and $L'$ to determine if $L$ dominates $L'$ and label $L'$ therefore can be discarded.

Consider the extension set $\mathcal{E}(L')$ of all feasible extensions of $L'$ to the sink vertex $s$ in the graph. Let $cost$ be the cost resource and let $(L + \Epsilon)$ be the state resulting in extending $L$ with an extension $\Epsilon$. Then if

$(L + \Epsilon)_{cost,s} \leq (L' + \Epsilon)_{cost,s}, \; \forall E \in \mathcal{E}(L')$

holds, then $L$ dominates $L'$. Essentially it is tested that no feasible extension of $L'$ leads to a cheaper path than when extending $L$ with the same extension.

In practice it is not possible to consider all extensions explicitly. Therefore, sufficient criteria are introduced that involves comparing current state values in the labels.

## Disposable and Non-Disposable Resources¶

Consider the disposable resource with the REF

$S_{r,j} = \max \{ l_{r,j}, S_{r,i} + q_{r,ij} \}$

and the non-disposable resource with the REF

$S_{r,j} = S_{r,i} + q_{r,ij}$

where $q_{r,ij}$ is the consumption of resource $r$ when extending from $i$ to $j$.

The term disposable refers to the fact that the resource is free to dispose of, that is, there is no cost associated with accumulating more of the resource. This allows the resource to "fill-up for free" when comparing state and also let the resource fall into the resource bounding interval if it would otherwise fall short (the $\max$ term). On the contrary the non-disposable resource may fall short when calculating the extension leading to infeasibility.

For dominance purposes disposable resources behave nicely and $S$ dominates $S'$ at vertex $i$ when

$S_{r,i} \leq S'_{r, i}$

compared to non-disposable resources where $S$ dominates $S'$ at vertex $i$ when

$S_{r,i} = S'_{r, i}$

The dominance criteria of disposable resource are much stronger than that of non-disposable resource, hence more labels can potentially be discarded using disposable resources. It is strongly recommended to use disposable resource when possible.

## Custom Resources¶

Custom resources are basically placeholders for state to be manipulated in callbacks. Use custom resources to implement advanced REFs and dominance criteria.

$S_{r,j} = S_{r,i}$
and the dominance criteria defaults to true. The latter ensures that custom resources do not constrain labels in any way.