# 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

and the *non-disposable* resource with the REF

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.

Advanced REFs Using Callbacks

A REF for a resource may depend on other resources values. This is known as an *inter-dependent resource*.

*Accumulated resource dependent cost* are often meet in time-dependent problems. This involves a sophisticated dominance criteria.

The REF of a custom resource defaults to

$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.