What kind of data structure should be used to store labels when implementing a labeling algorithm?

Question

The shortest path problem with resource constraints is a common subproblem when doing column generation. It is often solved with a labeling algorithm. The procedure is very well explained here and here.

To avoid complete enumeration, dominance is crucial. To check if one label dominates another, their resources need to be compared. Hence one is potentially going to check a newly created label against a huge number of other labels. That would imply that having a data structure that stores the labels sequentially in memory to so going through them is efficient as one can benefit for prefetching. However, it would also be beneficial to have the labels stored according to one or more resource, because then one can possibly stop looking for a dominating label early and hence skip many dominance checks. Having them stored makes it necessary to have a data structure that makes random insertion possible and efficient. That does not fit well with having sequential memory. Also, since an unprocessed label might get dominated, it should also be possible and efficient to erase arbitrary labels from the data structure.

Since reconstruction of the optimal path requires that a label store a pointer to the previous label, the pointers also need to stay valid when new labels are added and already existing labels being dominated and deleted.

I realize that a perfect data structure for this is difficult(if not impossible) to make, but what do the state of the art implementations use when doing this?

I use C++ for performance, so references and advice suitable for C++ are welcomed.

Answer 1

I have experience in writing the code implementing the labelling algorithm used by VRPSolver (https://vrpsolver.math.u-bordeaux.fr). You are right: it is advantageous to keep labels in a contiguous memory to benefit from using the cache. We keep labels in vectors (we called them "buckets"). There should be no dynamic data structures (pointers) inside labels. As suggested by @prubin, labels in a bucket are sorted by a resource consumption (in our case, by cost). When you want to insert a new label to a bucket, you start dominances checks from the first element and continue until you find that the new label is dominated or until you find the right place for it. In the latter case, you insert the label and you shift the remaining labels one by one in the memory while verifying at the same time whether they are dominated by the new label. You may potentially do many label copies while doing that, but copying labels is not expensive. The complexity of the algorithm does not change from such copies, as you need to check every label for dominance anyway.

We do not keep pointers to previous labels as they may be displaced in the memory. Instead we keep the ID of the bucket where the previous label is stored and the ID of the label in it. So, retrieving the path from a label is more expensive than when you keep pointers to previous labels. But anyway, the time to retrieve the paths is largely dominated by the running time of the labelling algorithm itself.

The bucket structure of the labelling algorithm is described in this paper: https://pubsonline.informs.org/doi/abs/10.1287/trsc.2020.0985. Unfortunately, it is not common in our community to present implementation details in papers. As you can see, sometimes such details are useful.

Answer 2

I can't speak to "state of the art implementations", but I would store the labels in lexicographic order of resource levels. Let's say vector $x$ is our new label and we want to see if it is dominated by any existing label $y^{(1)} \prec y^{(2)} \prec \dots \prec y^{(n)},$ where $\prec$ means "lexically less than" and, for dominance purposes, smaller is better. We compare $x_i$ to $y^{(1)}_i$ for $i = 1, 2, \dots$ until either we find an $i$ where $x_i < y^{(1)}_i$ or discover that $y^{(1)}$ dominates $x$ (in which case we are done). Assuming $x$ is not dominated by $y^{(1)}$, we move on to $y^{(2)}$ and repeat the process. If we reach the point where $x$ would fit in lexicographic sort order, we know $x$ is not dominated, and we scan the remaining labels to see if $x$ dominates any of them.

As far as how to implement this, I use Java, not C++. In Java, I would define a comparator to implement $\prec$ and use a TreeSet based on that comparator. I suspect C++ has similar critters.