{"entities":{"Q911990":{"pageid":913838,"ns":120,"title":"Item:Q911990","lastrevid":49371208,"modified":"2026-01-07T01:23:38Z","type":"item","id":"Q911990","labels":{"en":{"language":"en","value":"Classification of travelling salesman problem formulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4143779"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$B2193CD3-8359-4FE4-AD1B-C2BFB41D861D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aafca40adcb3455e872106638b00320a74374718","datavalue":{"value":{"text":"Classification of travelling salesman problem formulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q911990$1867E4DE-B918-4C82-ADC0-464E27052839","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"065acaae9ad381babb2be15182c67eaa6b7bd0f2","datavalue":{"value":"0697.90057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$6DA17808-02F9-4328-9EFA-C0038184DAD7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d32fa7a119075acf69a0c44641b7dab2b79cb35","datavalue":{"value":"10.1016/0167-6377(90)90052-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$AAFE553D-DF6F-46D8-BAE9-7C3101253CE1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"72ac426bf240ebf81d5640b79460b7af31d2a10f","datavalue":{"value":{"entity-type":"item","numeric-id":336354,"id":"Q336354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$46E6F2AB-78C4-45FD-A43E-380AB26EA430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"33fd9ca2317bf13b6f5b124a2b9103d0b54bc2ab","datavalue":{"value":{"entity-type":"item","numeric-id":319584,"id":"Q319584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$69A65CF4-3BD2-4C10-8814-C0529A247905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e70d3bdee72060c6616c893154335b33d6fe42d5","datavalue":{"value":{"entity-type":"item","numeric-id":339691,"id":"Q339691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$3794A52B-640E-4D1A-B76C-E0551BBD07F4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$E79C9A77-1A0C-40D9-8F24-3D6EBC04938D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q911990$AF43560C-6106-4FA1-B5D0-254F0EBD7FE0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8013f001fb1cf8b57e6287b60539e6df08a679b5","datavalue":{"value":"This paper compares various Traveling Salesman Problem formulations. With respect to the bounds given by the linear programming relaxations, it is known that the classical formulation of \\textit{G. B. Dantzig} et al. [Oper. Res. 2, 393-410 (1954)] is equivalent to the 2(n-1)-commodity flow formulation of \\textit{R. T. Wong} [Proc. IEEE Int. Conf. Circ. Comp., 149- 152 (1980)]. The authors show that this is also true for various recent 2(n-1) and (n-1)-commodity flow formulations based on Wong's formulation, and that these formulations are superior to the 1-commodity flow formulation of \\textit{B. Gavish} and \\textit{S. C. Graves} [Working paper GR- 078-78, ORC, MIT (1978)] and the 2-commodity flow formulation of \\textit{G. Finke, A. Claus} and \\textit{E. Gunn} [Congr. Numer. 41, 167-178 (1984; Zbl 0697.90056)].    Some remarks are also provided on the relative values of the formulations with respect to the number of variables and constraints.","type":"string"},"datatype":"string"},"type":"statement","id":"Q911990$ABCA3A70-98CB-43E1-918A-6376C0166353","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$0DBFA31A-C7A6-4555-9D06-D5E4B7FE754E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$EAF165A5-7445-41D5-B9A9-3BCA58B16EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$587DB97D-EE1D-43F7-9DDC-2FE0E35C83CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$186AF217-551F-483A-BFBD-C3545F8EFEDC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"32cccf713b8b22b8b370f8511753e06983064dbf","datavalue":{"value":"4143779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$991E9CF1-9940-40A8-95E6-A2B42B7F78AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e513e0e4a2f9fe9c2e9add88e515ac966218b3d6","datavalue":{"value":"Traveling Salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q911990$6ACDD99C-56FB-4F96-88BB-E18A2D11E782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"126420a03529ad338c39ee267bd5297100f94878","datavalue":{"value":"linear programming relaxations","type":"string"},"datatype":"string"},"type":"statement","id":"Q911990$C28E141E-AD72-48A7-8551-7E4117B8B1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d65232b737a604941dd453981a06a62ec4da6b1","datavalue":{"value":"commodity flow formulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q911990$9F243EE0-2C3C-4BCA-A093-DF0028FEE36D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6b6816c3de7983b793bf4c42808a1cb69f396cb6","datavalue":{"value":{"entity-type":"item","numeric-id":342501,"id":"Q342501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$257E069D-3850-4ABB-8D33-FB9B0274DF39","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$DC2A6F81-4D7C-4BFF-9F97-603772D3CD78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6c3e2af1c29e15fc45b62e79e1d51767a1143223","datavalue":{"value":"https://doi.org/10.1016/0167-6377(90)90052-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q911990$FB35DA35-E1F7-4D02-AB5E-D86FC10CC08C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f428410af86b5070a9a8da798114d877018f3d6c","datavalue":{"value":"W2001994662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911990$7FB20DB3-D7C1-441B-9800-2E063BE0287A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad64de6e7738e403b2afd1f2189b2425edff3d4b","datavalue":{"value":{"entity-type":"item","numeric-id":3315280,"id":"Q3315280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$DDB86B06-8D44-49CB-A769-28880C199BC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde83dc2358b044be23eaeb3226ac019d5e33e09","datavalue":{"value":{"entity-type":"item","numeric-id":5378639,"id":"Q5378639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$314C2455-F668-48E0-B1B1-59A57751620D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a9d0bb094890894a55365f54b7916c5f80be60a","datavalue":{"value":{"entity-type":"item","numeric-id":3475129,"id":"Q3475129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$E58EFA89-8102-4FE6-A5E2-5A95777C0730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72a134db15f4f700696be3e885eb1ff3520dc44b","datavalue":{"value":{"entity-type":"item","numeric-id":3686412,"id":"Q3686412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$EE806F3C-61C0-4033-BD03-D4E6644A2746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6265c28cd876d184adb3d01d8a29ef78ecd3ecac","datavalue":{"value":{"entity-type":"item","numeric-id":3753823,"id":"Q3753823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$55479234-088A-4DD2-B578-D21B4B28F3AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5b903864765fb40a5b80f7f222eabf61ff3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":5641007,"id":"Q5641007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$E7D674E0-7E96-46F5-AFCF-553A082BA812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cdc8ab92d92234a6c60e69beca185042cc554d5","datavalue":{"value":{"entity-type":"item","numeric-id":3281501,"id":"Q3281501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911990$DB232AB2-85A8-436C-B8E6-97F5EAA870B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1454546fe918402ab736c2573f679546f15836ca","datavalue":{"value":{"entity-type":"item","numeric-id":5297404,"id":"Q5297404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61c01923265bcd5be4c97df66caa3bb7bc111d03","datavalue":{"value":{"amount":"+0.8481329083442688","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q911990$31E93684-08B0-49FF-9985-7117810523E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d82ed1cb2e7e6327110e7090c5a1f10f1b8fd2b3","datavalue":{"value":{"entity-type":"item","numeric-id":3475129,"id":"Q3475129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90653e38964a95e772a4e91609e4cbaf3e25a4eb","datavalue":{"value":{"amount":"+0.8285923004150391","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q911990$D2677182-8D78-4E16-B239-F58219ECD27A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"600cf15641a1893bf4b6657f6bab3bd2b6fa7fe7","datavalue":{"value":{"entity-type":"item","numeric-id":955595,"id":"Q955595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4e9e7802cdf6c3ac939f1fd19dbe097a36a7a86","datavalue":{"value":{"amount":"+0.8260392546653748","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q911990$135CE2E0-B8EF-4FE3-8152-3C65C342D19C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5942779bd0c547e5197301c0335933a42b3282cf","datavalue":{"value":{"entity-type":"item","numeric-id":3217891,"id":"Q3217891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a0c993afe9834a03ab0c877c5806980854a0ee5","datavalue":{"value":{"amount":"+0.8174957036972046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q911990$26D2F991-8285-43A8-925B-2DC0D80AB5F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffcd37ac29bcc1d73a2469b0e729aabce3d3849b","datavalue":{"value":{"entity-type":"item","numeric-id":3141769,"id":"Q3141769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81491463bb49db8c9c4028a8e48c9e5e5673670c","datavalue":{"value":{"amount":"+0.803249716758728","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q911990$D48F1057-F4EB-4E48-A92A-8B661475031E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:911990","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:911990"}}}}}