Lien pour le webinaire
Nº du webinaire : 921 0104 9692
Code secret: 702645

The Traveling Salesman Problem minimizes the total distance of a tour through a number of cities. Adding Precedence Constraints compels the salesman to visit some cities before the others, which is often called Sequential Ordering Problem and occurs in logistics (first collect a parcel, then deliver it), warehousing (never stack dumbbells on top of crystal), industry (first drill a hole, then thread it), and so on, often with more constraints on top.

State-of-the-art exact solutions are based on mixed integer-linear programming models, but for certain specific instances, a special variety of dynamic programming (DP) works very well. In this talk, I will describe the theory that identifies these instances—with the aid of finite ordered sets—and show how it helped to close two instances from TSPLIB, ry48p.3.sop and kro124p.4.sop, which stood undefeated for more than a decade, and also how DP lends itself to branch-and-bound hybridization and parallel strategies.

In addition, the methods derived from DP are nice in that their complexity is broadly the same for different objective functions and even for time or (past) sequence dependent problems. These are, say, Restricted DP, a heuristic that is dependably better than nearest neighbor, but also benefits from DP's general complexity reduction and ability to use constraints to narrow the search space, and DP/branch-and-bound hybrid, which uses upper and lower bounds to prune the search space.