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.
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.
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.
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 when extending that resource from to can be described as
Resource bounds are defined in the interval for each vertex (or edge), and an extension is feasible if .
In the dynamic programming algorithm a dominance check is performed between two labels and to determine if dominates and label therefore can be discarded.
Consider the extension set of all feasible extensions of to the sink vertex in the graph. Let be the cost resource and let be the state resulting in extending with an extension . Then if
holds, then dominates . Essentially it is tested that no feasible extension of leads to a cheaper path than when extending 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 is the consumption of resource when extending from to .
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 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 dominates at vertex when
compared to non-disposable resources where dominates at vertex when
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 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
and the dominance criteria defaults to
true. The latter ensures that custom resources do not constrain labels in any way.