Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem

• We present several new formulations for the classical “Sequential Ordering Problem”.
• Two interesting families of equations are useful to strengthen the linear programming relaxations.
• We prove that the linear programming relaxations of the new formulations give good bounds.
• We analyse computational results to compare the known and new formulations.
• The paper also addresses the capacitated variant of the problem.

The sequential ordering problem (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a multi-commodity flow (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables and adding valid equations. We then use polyhedral projection, together with some known results on flows, cuts and metrics, to derive new families of strong valid inequalities for both problems. Finally, we give computational results, which show that our findings yield good lower bounds in practice.