{"entities":{"Q378087":{"pageid":379854,"ns":120,"title":"Item:Q378087","lastrevid":61383753,"modified":"2026-04-10T23:01:27Z","type":"item","id":"Q378087","labels":{"en":{"language":"en","value":"A branch-and-cut algorithm for the maximum benefit Chinese postman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6225197"}},"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":"Q378087$C4F991C7-05C7-4DDD-A1D2-8DAD75BCD948","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"19c447a5ac37f96cd813d9cbc26de40fb342c031","datavalue":{"value":{"text":"A branch-and-cut algorithm for the maximum benefit Chinese postman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q378087$003BC6CC-82AD-4B6B-8393-BE910C6D4A8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd5f6299e11efba025a8a43b9d72f0260807c4e4","datavalue":{"value":"1295.90108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378087$10AC995D-41C8-4717-8A6E-AA373E039B4C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e16ea5aa4e3033c95bfd37e69ac3b3606c8cbc7f","datavalue":{"value":{"entity-type":"item","numeric-id":321106,"id":"Q321106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$A5F3338B-9B52-43AB-A458-05392DA71F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"732de474c5d8189ec91317e47228153053f1e9fc","datavalue":{"value":{"entity-type":"item","numeric-id":319963,"id":"Q319963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$38C0296F-1307-4A57-A8CD-24FABFB0C4EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b41474a7330107d49cd4603abe1af1196ce10768","datavalue":{"value":{"entity-type":"item","numeric-id":185369,"id":"Q185369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$BBBE227B-797B-4194-8CB7-E7CB0C0F839D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec0bdebd65c9cd9ca1a69503de1064391386b616","datavalue":{"value":{"entity-type":"item","numeric-id":185371,"id":"Q185371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$0A9098C1-B527-4407-80C0-59BF8042DA7D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$8E6B9F17-9C67-48F6-92AE-926153DA6375","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9da4a2887762bfc0135842b48e115e887ee73eaa","datavalue":{"value":{"time":"+2013-11-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q378087$0FDD05A6-9599-46D9-A48D-F67A8B099766","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2814b60f19d97f7452af571ad5c3b5d58502d669","datavalue":{"value":"This article studies a variation of the undirected Chinese Postman Problem which considers several benefits associated with each edge. The objective function of the problem is to find a closed walk which maximize the total benefit. The article begins with an overview of the literature associated with this problem and the mathematical formulation of the maximum benefit Chinese postman problem which is in the form of an integer program. The authors then study the associated polyhedron defined by the inequalities and several types of valid inequalities are derived and proven. A branch-and-cut algorithm is then described and the separation algorithms for the proposed cuts are provided. The article concludes with the results of the numerical experimentation which was performed using the CPLEX optimizer on test instances generated by the authors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q378087$E0BE689B-4BB7-4677-8156-19F7F8C0B682","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58309c80337e7309a39fa8b39c69e1b722b3cd2b","datavalue":{"value":{"entity-type":"item","numeric-id":590170,"id":"Q590170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$93E4A266-B671-4896-AD24-10BFDFFC0138","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378087$512D5054-A4C3-4EF0-AA59-2D043571C20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378087$4AC286CD-DD26-43D8-B6FF-3C47EA1CD6BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ba150a551f161ebe29f2413183cdda4c24f66f0","datavalue":{"value":"6225197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378087$4B653080-6E4F-4101-8686-FF55354BE37D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"286e3b049fdd4786d44b32e11112e471b0ca7699","datavalue":{"value":"Chinese postman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q378087$57C15221-E8E2-4B35-B620-5783A8CF2F4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73e8ea576307e9e4d85fbc574c77b4dde284a643","datavalue":{"value":"maximum benefit Chinese postman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q378087$99235B93-CA29-45E5-B17F-DC4BB2F1FFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e81f83acf92ff267f0120709014fc50f24dbd040","datavalue":{"value":"rural postman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q378087$972DAE5E-3820-4101-B681-E74F1D80FBAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"747d0307b6dafcec6e50ba81d3396bbf3812302c","datavalue":{"value":"facets","type":"string"},"datatype":"string"},"type":"statement","id":"Q378087$76AA09FF-ABAF-4912-98E8-F9F2160CF00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89e0547bc5170c50b4b1aab6a2fb0a2fef9af5ca","datavalue":{"value":"branch-and-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q378087$EDD92242-060E-40A0-AB9C-FB648869F4F5","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4d0306a541ac4d64d413698a8167f6dce4fa4ce8","datavalue":{"value":{"entity-type":"item","numeric-id":16269,"id":"Q16269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$7F537907-6A72-4E61-BBF7-2D0265FA29C6","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":"Q378087$54A88469-5C39-41F9-B49A-98695EF8E2AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0dc4f6ce65f8c56dbbd6753d2a4b2a31bb47c86d","datavalue":{"value":"https://doi.org/10.1007/s10107-011-0507-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q378087$791E8870-0932-4D9C-81D1-7731AFEF1FCB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9fb9482fbe8aa9c3d16b470a69d3cc585d9198ed","datavalue":{"value":"W1997409263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378087$79BF83D4-CFEB-429D-9FE9-91897DF75A99","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1690f0de289d0a77b7640edd6caf09a06f05d959","datavalue":{"value":{"entity-type":"item","numeric-id":1041930,"id":"Q1041930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$9A2CF0C1-1BBA-4609-851C-A30DD3539D9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f97b8da31d9139a6d0e23af192344088e6ac21a2","datavalue":{"value":{"entity-type":"item","numeric-id":2496044,"id":"Q2496044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$8EFE0EAB-FA48-4F27-B425-87FE976C010F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2befd36702fcf249e36cdcb42e08abe4548c00b9","datavalue":{"value":{"entity-type":"item","numeric-id":975994,"id":"Q975994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$8FACB07D-7EFE-4A0D-9A1E-7E09CCB36A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3be975c66d7175c7bcf1d2da2353e25f3e227505","datavalue":{"value":{"entity-type":"item","numeric-id":1078187,"id":"Q1078187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$ADD47164-4128-46E8-AF72-3341C59BFFFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12aaa98f03cc9fece3c294566b5105aed7039933","datavalue":{"value":{"entity-type":"item","numeric-id":5935711,"id":"Q5935711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$E9AE3C50-8768-40F0-9B2B-B9B3287B703A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"589934c87043b084333e95605981790350975b30","datavalue":{"value":{"entity-type":"item","numeric-id":5295483,"id":"Q5295483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$33234637-3FAD-4C56-ACE2-4F974030214A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"862e7e2d79c1c80f009125416561b5958fde13fa","datavalue":{"value":{"entity-type":"item","numeric-id":2494509,"id":"Q2494509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$7F9CB6D3-49DA-4CB4-9506-18242FCCBCFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd08a0d7557f66ff93ff4e03e8770ab732af6c89","datavalue":{"value":{"entity-type":"item","numeric-id":1342042,"id":"Q1342042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$199095B9-3DE0-47F9-A988-C5C5CFC601D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de990f59feb111d5a2cb7b71cfad73cf42ec33f7","datavalue":{"value":{"entity-type":"item","numeric-id":1575070,"id":"Q1575070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$44CC475C-CD06-44FA-B06C-8AA9ABECBDB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4e5c165b27a8c400c619f85f58908fa263e6f2b","datavalue":{"value":{"entity-type":"item","numeric-id":4143017,"id":"Q4143017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$0FB8F780-3618-4B75-9B4C-8D8981E07786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b6051cd2682e72dedc8ebcdf1ccd709271aaa6","datavalue":{"value":{"entity-type":"item","numeric-id":3648510,"id":"Q3648510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$5A4D5295-D219-45ED-A246-E177FF167304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e56473c89ad4a206916cdb9bf3cd9852ca13cf1c","datavalue":{"value":{"entity-type":"item","numeric-id":1261382,"id":"Q1261382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$B8CDB2C3-2BCA-4708-8E54-E139079A454C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1e8c199d0a3738b5df7039fa423628b9c9f24f","datavalue":{"value":{"entity-type":"item","numeric-id":4040221,"id":"Q4040221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$1AE1E73F-1BC5-42D5-9931-7617C66C7241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5dc62bad8d8b348530b78b3cb920a547157072d","datavalue":{"value":{"entity-type":"item","numeric-id":4145183,"id":"Q4145183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$EEF6F6C8-BB0F-48FF-AE54-C360E946D08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac95765438a82787f030f1788d515422a72721d0","datavalue":{"value":{"entity-type":"item","numeric-id":5426612,"id":"Q5426612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$36776AA9-7269-4222-AA8F-4ED775289189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb0764e7961cb8f5b37d002fe6fca339c6c49143","datavalue":{"value":{"entity-type":"item","numeric-id":5317556,"id":"Q5317556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378087$F1965DA5-7D6D-4FF2-96B6-6B5B805EC66C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"27fb9d7cdfe85301caef7c1fdd15f579848b01a5","datavalue":{"value":"10.1007/S10107-011-0507-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378087$17A1F698-5E14-42C2-B4BE-84E66A08F461","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e11ec6063f64789b968e360290166119b68b9936","datavalue":{"value":{"entity-type":"item","numeric-id":5092514,"id":"Q5092514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2871bcba1700d11fe840a496851625c39b10d48","datavalue":{"value":{"amount":"+0.8427310585975647","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":"Q378087$3C4EDD98-6B0A-40E5-8C48-E0485FA2C3B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2cbd12ce5e879a80815cb3ad8540efe3f6cba34","datavalue":{"value":{"entity-type":"item","numeric-id":1261382,"id":"Q1261382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ddd853104432520da8b76c8a00c0cb3278e293a","datavalue":{"value":{"amount":"+0.8374638557434082","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":"Q378087$F61068EA-099E-4DDA-8955-4DD679482048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"126da685f9d867a9649b3aa57464509a4d13fe34","datavalue":{"value":{"entity-type":"item","numeric-id":5426612,"id":"Q5426612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ad1b58a66b5d9a7414a54a5bf719a8ea387d873","datavalue":{"value":{"amount":"+0.8350450396537781","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":"Q378087$5C3170DE-2D76-4EF9-9996-D57D6028FA0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b83c8546dba6b8c52c87f4d043749fd6c4a7c7a1","datavalue":{"value":{"entity-type":"item","numeric-id":1575070,"id":"Q1575070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52634de172d626c8c95c551302d278a0d5d9ad4e","datavalue":{"value":{"amount":"+0.8059748411178589","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":"Q378087$7E87DA57-67A5-4777-A248-C0F13C574433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7dc2c162775e40927f009cc8f66c7a8b513751f","datavalue":{"value":{"entity-type":"item","numeric-id":4887738,"id":"Q4887738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55cfbc9ca42fc272222aa48b6120deb61bc74980","datavalue":{"value":{"amount":"+0.7856955528259277","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":"Q378087$6ADD0B2F-5BA0-4FCD-9198-E53DE30A333A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A branch-and-cut algorithm for the maximum benefit Chinese postman problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_branch-and-cut_algorithm_for_the_maximum_benefit_Chinese_postman_problem"}}}}}