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.
multi-commodity flows sequential ordering travelling salesman problem with precedence constraints metrics polyhedral combinatorics