{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T00:54:28Z","timestamp":1768006468163,"version":"3.49.0"},"reference-count":16,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4120,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1995,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The task of developing daily schedules for a steel rolling mill has been 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\u2010cost tour including enough cities to collect a required amount of prize money. This paper addresses the facial structure of the PCTS polytope, the convex hull of solutions to the PCTS problem. In an earlier paper, we generalized to the PCTS polytope the subtour elimination inequalities for the Asymmetric Traveling Salesman (ATS) polytope. Here, we give a general method for deriving a facet defining inequality for the PCTS polytope from any facet defining inequality for the ATS polytope. We apply the procedure to several well\u2010known families of facet inducing inequalities for the ATS polytope: comb, odd CAT, SD, clique tree, and lifted cycle inequalities. We also extend the cloning and clique lifting procedure for the ATS polytope to the PCTS polytope.<\/jats:p>","DOI":"10.1002\/net.3230250406","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T20:18:36Z","timestamp":1179001116000},"page":"199-216","source":"Crossref","is-referenced-by-count":35,"title":["The prize collecting traveling salesman problem: II. Polyhedral results"],"prefix":"10.1002","volume":"25","author":[{"given":"Egon","family":"Balas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"E.Balas The prize collecting traveling salesman problem. ORSA\/TIMS Meeting in Los Angeles (spring1986)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190602"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0402038"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.4.1001"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581274"},{"key":"e_1_2_1_7_2","series-title":"Proceedings of the Third IPCO Conference, Erice","first-page":"23","volume-title":"Integer Programming and Combinatorial Optimization","author":"Balas E.","year":"1993"},{"key":"e_1_2_1_8_2","unstructured":"E.BalasandC. H.Martin Combinatorial optimization in steel rolling (extended abstract).Workshop on Combinatorial Optimization in Science and Technology (COST) RUTCOR (April1991)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.16.1.42"},{"key":"e_1_2_1_10_2","unstructured":"M.Fischetti Clique tree inequalities define facets of the asymmetric traveling salesman polytope. DEIS University of Bologna Technical Report OR\/89\/7 (1989)."},{"key":"e_1_2_1_11_2","first-page":"319","volume-title":"Vehicle Routing: Methods and Studies","author":"Fischetti M.","year":"1988"},{"key":"e_1_2_1_12_2","volume-title":"Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme","author":"Gr\u00f6tschel M.","year":"1977"},{"key":"e_1_2_1_13_2","first-page":"251","volume-title":"The Traveling Salesman Problem: A Guided Tour to Combinatorial Optimization","author":"Gr\u00f6tschel M.","year":"1985"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.11.4.537"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580222"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.4.833"},{"key":"e_1_2_1_17_2","unstructured":"ROLL\u2010A\u2010ROUND:A System for Scheduling Steel Rolling Mills. Copyright Balas and Martin (1986)."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230250406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230250406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T18:36:56Z","timestamp":1698259016000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230250406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["10.1002\/net.3230250406"],"URL":"https:\/\/doi.org\/10.1002\/net.3230250406","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}