{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,26]],"date-time":"2026-04-26T01:37:46Z","timestamp":1777167466916,"version":"3.51.4"},"reference-count":16,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":9263,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1981,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It is well\u2010known that few combinatorial optimization problems can be solved effectively by dynamic programming alone, since the number of vertices of the state space graph is enormous. What we are proposing here is a general relaxation procedure whereby the state\u2010space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem. This <jats:italic>state space relaxation<\/jats:italic> method is analogous to Langrangian relaxation in integer programming. This paper gives a survey of this new methodology, and gives, as examples, applications to the traveling salesman problem (TSP), the time\u2010constrained TSP and the vehicle routing problem (VRP). Valid state space relaxations are discussed for these problems and several bounds are derived in each case. Subgradient optimization and \u201cstate space ascent\u201d are discussed as methods of maximizing the resulting lower bounds. More details of the procedures surveyed in this paper can be found in [2, 3, 4].<\/jats:p>","DOI":"10.1002\/net.3230110207","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T12:00:18Z","timestamp":1178884818000},"page":"145-164","source":"Crossref","is-referenced-by-count":234,"title":["State\u2010space relaxation procedures for the computation of bounds to routing problems"],"prefix":"10.1002","volume":"11","author":[{"given":"Nicos","family":"Christofides","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Mingozzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Toth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Dynamic Programming","author":"Bellman R.","year":"1958"},{"key":"e_1_2_1_3_2","unstructured":"N.Christofides A.Mingozzi andP.Toth \u201cExact Algorithms for the TSP with Additional Constraints\u201d Imperial College Internal Report No. IC OR 80 23 September1979."},{"key":"e_1_2_1_4_2","unstructured":"N.Christofides A.Mingozzi andP.Toth \u201cState\u2010space Relaxations for Combinatorial Problems\u201d Imperial College Internal Report No. IC OR 79 09 July1979."},{"key":"e_1_2_1_5_2","unstructured":"N.Christofides A.Mingozzi andP.Toth \u201cExact Algorithms for the Vehicle Routing Problem Based on Spanning Trees and Shortest Path Relaxations\u201d Math. Program. to appear."},{"key":"e_1_2_1_6_2","volume-title":"Combinatorial Optimization","author":"Christofides N.","year":"1979"},{"key":"e_1_2_1_7_2","unstructured":"M.Fisher \u201cLagrangian relaxation Methods for Combinatorial Optimization\u201d Paper presented at Summer School in Combinatorial Optimization Urbino Italy 1978."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(71)90106-5"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00935190"},{"key":"e_1_2_1_10_2","volume-title":"Integer Programming","author":"Garfinkel R.","year":"1970"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120690"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580223"},{"key":"e_1_2_1_14_2","volume-title":"The Traveling Salesman Problem and Shortestn\u2010paths","author":"Houck D.","year":"1977"},{"key":"e_1_2_1_15_2","volume-title":"Dynamic Programming and its Applications","author":"Morin T.","year":"1978"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.231"},{"key":"e_1_2_1_16_3","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.2.179"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230110207","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230110207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T11:41:36Z","timestamp":1699789296000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230110207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,6]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1981,6]]}},"alternative-id":["10.1002\/net.3230110207"],"URL":"https:\/\/doi.org\/10.1002\/net.3230110207","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,6]]}}}