{"entities":{"Q3714901":{"pageid":5744807,"ns":120,"title":"Item:Q3714901","lastrevid":110528867,"modified":"2026-11-17T14:22:41Z","type":"item","id":"Q3714901","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3943560"}},"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":"Q3714901$E6CB4D85-BD5C-4FBD-8667-4949A2F67735","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fd04c5012bfa0b4824dfa91dd102004404d2c222","datavalue":{"value":"0587.90074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3714901$376A65F9-51AB-41F0-8474-7A3B99EB76AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"afb20ad30ffa52e0802e4180df09a4ca34fccf7f","datavalue":{"value":{"entity-type":"item","numeric-id":189591,"id":"Q189591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3714901$A8E6FFCA-5171-4D9F-AB16-4CB7FBF91A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c79d63a974620aa9dd22e3cdec2e56a2714b61d9","datavalue":{"value":{"entity-type":"item","numeric-id":202055,"id":"Q202055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3714901$797780D8-FC14-4B06-BBC1-65714A543F52","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q3714901$B6F14E01-9E09-486A-91E5-13AF5B1EE4B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3714901$94881BBC-786A-4C87-BD55-0E4FB851106C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3714901$076FC5ED-3BBB-418F-A61D-3B5E1EB2DF4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3714901$5FEFCA65-91F8-4225-B8C1-DFB619D6DDC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a1999bd8089c5e33b052b0e408a6a7edea2b3742","datavalue":{"value":"90-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3714901$7BD71D86-32B3-4C16-94A5-24994DB62504","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5ed69492e3fe04ebebb50247fae3c41430a0345","datavalue":{"value":"3943560","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3714901$47EDF114-6AC6-4677-A4E1-0C6E21509380","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"421a43f4b0e8832a026eaa34353c95869f115bee","datavalue":{"value":"survey","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$110DDD97-1E82-4D30-99F4-7194459BC1CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a775bb96e661de6e014656e102c717a4436a71d7","datavalue":{"value":"computational aspects","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$2D47DB23-84B5-489E-8102-17E9A3822A81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c162d92b244f46ccc5ab4927c2f941587cfbdce","datavalue":{"value":"polyhedral theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$52CE6524-3117-4687-86A1-CBDEB3920A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$027AA1D2-1563-46EF-80FC-FBA77B83846F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"995e65f6eee928a322639f2e264c9b7e46dd551d","datavalue":{"value":"facet-including linear inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$1C8F811D-535E-462A-90ED-00266E37E423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5bbd8c55216bc58296fa2ade785c5de51a5a6c4","datavalue":{"value":"cutting plane algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$C62853E3-0DB3-4FE6-889B-E008CC2206AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5b67b504fe8fa4d7283e8e450ab4587f34dca82","datavalue":{"value":"ellipsoid algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$652FF742-8F58-4497-99CA-5635BA40A9B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01044b0df236903f60718f903798f50b4cf21524","datavalue":{"value":"subtour elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$4E50AE3A-3D7C-43A6-AA0C-EB9D540096ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e4291623258e1161a74163c51ecc17eadc1c82","datavalue":{"value":"clique tree inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$B8FABFF2-838D-4888-A685-580F230665EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c535f0240ef8dd12dc37b9dec31cff482bdfcf38","datavalue":{"value":"Heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$E11BBC64-F05E-411F-9C5B-808A408BBE4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$37FAD485-B827-4606-99C7-1B8F4A00EBE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"438acbc5a09da693ba92d1636d1c96d2c3e9eed8","datavalue":{"value":"relaxation method","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$9FD6D26D-A0B5-428E-ABB1-E5F8A3D1176F","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":"Q3714901$E6F86BC4-7703-4F0C-9600-5AA585D555A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6968ddaeb1ff5a613adffc905bde5b1eba36ee51","datavalue":{"value":{"entity-type":"item","numeric-id":918865,"id":"Q918865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d3af3dd3e0608e91c7765a4f4143b49fbd4871f","datavalue":{"value":{"amount":"+0.8972253203392029","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":"Q3714901$22C73268-1A5B-41DB-A113-56C3A9EFA197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97c6a0cba5cc451dec6180629069752591c7b06a","datavalue":{"value":{"entity-type":"item","numeric-id":3714900,"id":"Q3714900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d6e0fe3fc2755be254c79879c53d5da20548bcd","datavalue":{"value":{"amount":"+0.839675784111023","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":"Q3714901$E357E2AD-F87E-4255-803F-E594CDC49DC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65c024cb13663fed2d0040e3281584b082f566e9","datavalue":{"value":{"entity-type":"item","numeric-id":4414643,"id":"Q4414643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"219da45f0440eccab179bf2bea1953bcc616d7c1","datavalue":{"value":{"amount":"+0.8222490549087524","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":"Q3714901$613740DC-2BD0-4C80-9614-EB9644C5E418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"418cfbc305395f3bc3d879ad1ef194931041d40a","datavalue":{"value":{"entity-type":"item","numeric-id":3030581,"id":"Q3030581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8917a56d8222558f98d6763be907792bf664a78d","datavalue":{"value":{"amount":"+0.816351056098938","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":"Q3714901$BDDDEAA8-FBA3-4C23-B86A-D9AE133C4A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d926dddaaf5ffb40cfa001fe05484f11c4d53df","datavalue":{"value":{"entity-type":"item","numeric-id":3813613,"id":"Q3813613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42229bdc2acb6b716d2f73ca4a12b8806cf9e57f","datavalue":{"value":{"amount":"+0.8161821961402893","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":"Q3714901$9863FFAF-D6CD-4992-A466-6DFC97B9A456","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"78a9f7bb15ae38c2f5ef8bed51c3ebf865851ab7","datavalue":{"value":"[For the entire collection see Zbl 0562.00014.] This chapter focuses on the computational aspects of the polyhedral theory developed in Chapter 8 of this book [see the preceding review] for the traveling salesman problem. The problem is now that of finding facet- including linear inequalities to be used, for instance, in a cutting plane algorithm using linear programming techniques. The authors first study the number of facets of TSP polytopes. One does not know a complete system of facet-inducing inequalities, but it is even impossible to list all known ones, because of their huge number. Yet in order to prove optimality of a given vertex, one only needs a suitable set of facet-inducing inequalities. Suitable constraints (facet-inducing, rather than just valid inequalities) must be generated ''on the fly'' if one wants to use LP techniques. The authors discuss the equivalence of optimization and algorithmic facet identification, based on the ellipsoid algorithm. The next two sections deal with identification of subtour elimination constraints and of clique tree inequalities. Heuristic and exact (polynomial) procedures for the solution of the subtour problem are described. For the case of the general clique tree inequalities, the facet identification problem is not solved to date nor is there any nontrivial heuristic for it. However there are a polynomial algorithm and heuristics for identifying 2-matching constraints and there is a heuristic for comb constraints. The final section gives an account of what has been done in terms of applying the polyhedral theory for the TSP to numerical problem solving. The solution of a 120-city problem by a relaxation method without recourse to branch-and-bound is described in detail. Computation of lower bounds for 74 TSP's and solution of 10 large scale problems are then discussed. The authors point out that very few additional facet-inducing inequalities are needed in order to obtain excellent lower bounds on the minimum tour length and in some cases to prove optimality as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3714901$EB23BC74-F957-42E2-A593-C6872A9CC40A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3714901","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3714901"}}}}}