A note on the separation of subtour elimination constraints in elementary shortest path problems

• Presents alternative procedure for separating subtour elimination constraints.
• Procedure is based on computing the strong components of the support graph.
• Procedure has better worst-case time complexity than standard way of separating SECs.
• Moreover, procedure is easier to implement.
• Computational experiments verify practical usefulness of the procedure.

This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses maximum flow algorithms, and is easier to implement.