Skip to content

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 rr when extending that resource from ii to jj can be described as

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

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

Dominance

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

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

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

holds, then LL dominates LL'. Essentially it is tested that no feasible extension of LL' leads to a cheaper path than when extending LL 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

Sr,j=max{lr,j,Sr,i+qr,ij}S_{r,j} = \max \{ l_{r,j}, S_{r,i} + q_{r,ij} \}

and the non-disposable resource with the REF

Sr,j=Sr,i+qr,ijS_{r,j} = S_{r,i} + q_{r,ij}

where qr,ijq_{r,ij} is the consumption of resource rr when extending from ii to jj.

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\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 SS dominates SS' at vertex ii when

Sr,iSr,iS_{r,i} \leq S'_{r, i}

compared to non-disposable resources where SS dominates SS' at vertex ii when

Sr,i=Sr,iS_{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

Sr,j=Sr,iS_{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.