Exact approaches for the orderly colored longest path problem: performance comparison

In this paper we consider a particular graph-optimization problem. Given an edge-colored graph and a set of constraints on the sequence of the colors, one is to find the longest path whose colored edges obey the constraints on the sequence of the colors. In the actual formulation, the problem generalizes already known NP-Complete problems, and, evidently, the alternating path problem in edge colored graphs. Recent literature has shown several contexts where such problem may be useful to model interesting applications, and has proposed exact IP models and related algorithms. We extend on these existing models and extensively test new formulations for the problem, showing how one of the newly developed model clearly exhibits better performance, allowing to solve at optimality instances of significant sizes.