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

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.

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.