{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T23:11:46Z","timestamp":1780441906393,"version":"3.54.1"},"reference-count":13,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":6219,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1989,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every city that he vitis and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and net penalties, while visiting enough cities to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem (PCTSP). This paper discusses structural properties of the PCTS polytope, the convex hull of solutions to the PCTSP. In particular, it identifies several families of facet defining inequalities for this polytope. Some of these inequalities are related to facets of the ordinary TS polytope, others to facets of the knapsack polytope. They can be used in algorithms for the PCTSP either as cutting planes or as ingredients of a Lagrangean optimand.<\/jats:p>","DOI":"10.1002\/net.3230190602","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T03:49:01Z","timestamp":1178941741000},"page":"621-636","source":"Crossref","is-referenced-by-count":398,"title":["The prize collecting traveling salesman problem"],"prefix":"10.1002","volume":"19","author":[{"given":"Egon","family":"Balas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580440"},{"key":"e_1_2_1_3_2","unstructured":"E.Balas The prize collecting traveling salesman problem. Paper presented at the ORSA\/TIMS Meeting in Los Angeles April 14\u201316 (1986.)"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584228"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0134010"},{"key":"e_1_2_1_6_2","unstructured":"M.Gr\u00f6tschel Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme Hain (1977)."},{"key":"e_1_2_1_7_2","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimizations","author":"Gr\u00f6tschel M.","year":"1985"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580442"},{"key":"e_1_2_1_9_2","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"Lawler E. L.","year":"1985"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580222"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580121"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120888"},{"key":"e_1_2_1_13_2","volume-title":"ROLL\u2010A\u2010ROUND: Software Package for Scheduling the Rounds of a Rolling Mill"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580441"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230190602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230190602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T09:02:53Z","timestamp":1697965373000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230190602"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,10]]},"references-count":13,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,10]]}},"alternative-id":["10.1002\/net.3230190602"],"URL":"https:\/\/doi.org\/10.1002\/net.3230190602","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,10]]}}}