Abstract:
Symmetric traveling salesman problem (STSP), a difficult combinatorial problem is formulated as a multistage insertion (MI) decision problem in Arthanari and Usha (2000). MI formulation is a compact 0-1 formulation for STSP. MI has given rise to the definition of a combinatorial object called pedigree. Arthanari (2008) contains a necessary condition for a MI-relaxation solution to be expressible as a convex combination of pedigrees. The existence of a multicommodity flow with the optimum value equal to unity over some layered network is checked for this purpose. This paper walks through an illustrative example to show the construction of such a network and the procedures involved in checking the necessary condition. Another important feature of this example is it brings out the need for discarding some arcs from the network called dummy arcs, for the correctness of the necessary condition for membership.
