Scientific Program > Talks by Speaker > Leggieri Valeria

We present lifted polynomial length formulations that can be obtained using Reformulation and Linearization Techniques (RLT) from an initial ordered path-based formulation. The tightest formulation that can be derived using this process turns out to be equivalent to the strongest multi-commodity flow formulation presented in the literature by Letchford and Salazar-Gonzalez. In order to further strengthen the formulation, three sets of polynomial size valid inequalities are proposed. The first set is retried using precedence relationship between customers from the Traveling Salesman problem, the second set is obtained applying RLT on precedence constraints and the third set exploits the possible incompatibilities of the customers on the basis of their demands and of the capacity load of the vehicles. Finally, we present computational results with the aim of showing the tightness of the proposed formulation and the impact of the valid inequalities.