THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM .2. POLYHEDRAL RESULTS

The task of developing daily schedules for a steel rolling mill has be en formulated as a Prize Collecting Traveling Salesman (PCTS) Problem, in which a salesman who gets a prize for every city he visits seeks a minimum-cost tour including enough cities to collect a required amoun t of prize money. This paper addresses the facial structure of the PCT S polytope, the convex hull of solutions to the PCTS problem. In an ea rlier paper, we generalized to the PCTS polytope the subtour eliminati on inequalities for the Asymmetric Traveling Salesman (ATS) polytope. Here, we give a general method for deriving a facet defining inequalit y for the PCTS polytope from any facet defining inequality for the ATS polytope. We apply the procedure to several well-known families of fa cet inducing inequalities for the ATS polytope: comb, odd CAT, SD, cli que tree, and lifted cycle inequalities. We also extend the cloning an d clique lifting procedure for the ATS polytope to the PCTS polytope. (C) 1995 John Wiley and Sons, Inc.