torressa
commented
1 year ago Hi @felicze! Thanks for the detailed bug report. Indeed I completely missed this in the dominance checks, great catch, thanks! I would really welcome a PR on this as I don't have the bandwidth work on this for now. I am not sure if this affects performance, so maybe giving the user the ability to deactivate these checks would be good. Alternatively could just remove the 2-cycle check.
Describe the bug The non-elementary RCSP should always be shorter than the elementary version. However, in a column generation python prototype for a VRP variant, we observed that sometimes there is no non-elementary path with negative reduced cost, but there is an elementary path with negative reduced cost.
We managed to reproduce this behavior in C++ and found that 2-cycles are eliminated (forbidden) https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/labelling.cc#L158-L160
But 2-cycle elimination for non-elementary paths is not considered in the function for the dominance check https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/labelling.cc#L162
Short example: 0 - source, 11 - sink $\lambda_1$: label at node 8 with partial path 0-6-7-8, weight -270 $\lambda_2$: label at node 8 with partial path 0-1-3-4-8, weight -260 $\lambda_1$ dominates $\lambda_2$ as $W(\lambda_1) < W(\lambda_2)$ and $R(\lambda_1) \leq R(\lambda_2)$
A RCSP with neg. reduced costs is 0-1-3-4-8-7-6-11. This path cannot be found as $\lambda_2$ is dominated. Another path with neg. reduced costs would obviously be 0-6-7-8-7-6-11. However, this path cannot be found as 2-cycles are not allowed. As a result, no path with neg. reduced costs can be found. In contrast, elementary path 0-1-3-4-8-7-6-11 is returned when we prohibit non-elementary paths since $\lambda_1$ does not dominate $\lambda_2$ under elementary conditions ( $S(\lambda_1) \subseteq S(\lambda_2)$ with $S$ set of visited customers in partial path)
Suggestions There are several possibilities to include the correct dominance check and to ensure that both labels have the same feasible extensions, see for example section 5 in Irnich and Villeneuve. A simple, but not most effective way, would be to check if the both labels have the same predecessor. If not, the dominance rule cannot be applied, since both would have different feasible extensions. In the example above: $\lambda_1$ does not dominate $\lambda_2$ as both have different predecessors.