{"entities":{"Q1124710":{"pageid":1135459,"ns":120,"title":"Item:Q1124710","lastrevid":47427526,"modified":"2026-01-01T17:44:06Z","type":"item","id":"Q1124710","labels":{"en":{"language":"en","value":"An exact algorithm for large multiple knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1370758"}},"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":"Q1124710$BA281D70-3EF0-445B-AB62-5BBCD3D03110","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f90dc117c3c486be8fa87915de82454ae2ac48dc","datavalue":{"value":{"text":"An exact algorithm for large multiple knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124710$861AB9B2-5FEA-4BD7-B047-0ED5CE5D68F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"583c2d9316d4a25e4a967f0e578413d18015b925","datavalue":{"value":"0948.90110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$E8006968-69F6-4F96-A952-D6AF2CD4DBAC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dfa1e1cd345b864b63bd778ecf1e63251670e72c","datavalue":{"value":"10.1016/S0377-2217(98)00120-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$483A9C96-4C05-449A-BD4C-3D083E6A6202","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b872701bfb1dbb58ac5ab4dce200a4c7ff12af20","datavalue":{"value":{"entity-type":"item","numeric-id":168068,"id":"Q168068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$67437283-5640-4B6C-90A3-F88B80BE040B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$52BB67CD-F424-43F4-A8F3-8A6CB8F52A77","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"78e20c03e48a6255627731df72a8de183874315d","datavalue":{"value":{"time":"+2000-11-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1124710$0EA72669-0794-41A6-BDD7-74B68A16644E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ac9d8e1ed6225b57a461fc59baa6c9c88ada0bee","datavalue":{"value":"The Multiple Knapsack Problem (MKP) is the problem of assigning a subset of \\(n\\) items to \\(m\\) distinct knapsacks, such that the total profit sum of the selected items is maximized, without exceeding the capacity of each of the knapsacks. The problem has several applications in naval as well as financial management. A new exact algorithm for the MKP is presented, which is specially designed for solving large problem instances. The recursive branch-and-bound algorithm applies surrogate relaxation for deriving upper bounds, while lower bounds are obtained by splitting the surrogate solution into the \\(m\\) knapsacks by solving a series of subset-sum problems. A new separable dynamic programming algorithm is presented for the solution of subset-sum problems, and we also use this algorithm for tightening the capacity constraints in order to obtain better upper bounds. The developed algorithm is compared to the MTM algorithm by Martello and Toth, showing the benefits of the new approach. A surprising result is that large instances with \\(n=100 000\\) items may be solved in less than a second, and the algorithm has a stable performance even for instances with coefficients in a moderately large range.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124710$13257951-E5CB-4E30-9DF8-F0174EABAB54","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$D7D1BD15-E3A6-47D3-8C5A-8B73E3E6FDE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$17AAFD2A-4F9B-4034-A679-57D820201D2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$6D48B588-FE03-4A38-9F86-86DE20A50933","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0164ecd983c78f344652484a382adecc01e11f9","datavalue":{"value":"1370758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$6A8CCB82-DF6A-46DE-A4C6-06601395738F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124710$959F35CD-7708-4171-BB04-39C63A6B963E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124710$C24C6EA0-8555-47F1-AEF9-E2C2EDA368E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124710$86802F7B-9882-4643-BC01-6CC45E8FA254","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c6404998a03e67a82f9100811c979641f01d5a2e","datavalue":{"value":"Q58826495","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$9115838D-ED9D-4F86-864F-CC7BE2933AB9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a45b400d22190ce8d9d8376830240adc5a55cd78","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$CF7226CE-BBD1-484A-9D05-17FD57FE5418","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c999c1a7fc9dbe817177ebd058dccb9f0956e5fe","datavalue":{"value":{"entity-type":"item","numeric-id":16891,"id":"Q16891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$DD57B9F3-73A8-4489-863A-C2E22379C8FA","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":"Q1124710$400AE981-B0EC-4DC2-8DF6-AE000DB388C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d834b2f061333007e84559a210df1dabd1b7c737","datavalue":{"value":{"entity-type":"item","numeric-id":3993418,"id":"Q3993418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$381070A0-3CE4-4B4E-8841-D26BD1AE032B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1f0e502c3e1c6cb2b149a0a803e034ec61aea6f","datavalue":{"value":{"entity-type":"item","numeric-id":4282749,"id":"Q4282749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$9E97BB06-F04D-441B-A6F0-409935014B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1975591d5d9308514687af3d82e3e82fc5b342d6","datavalue":{"value":{"entity-type":"item","numeric-id":4175050,"id":"Q4175050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$3945E0DE-24E5-42A9-8269-DDADE1E34423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48e85d6c8d64b152510eb4508c01159ec937252d","datavalue":{"value":{"entity-type":"item","numeric-id":1142701,"id":"Q1142701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$18810509-B1FF-436B-8A2F-6D7CA4563294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a289a6ea21b826b2156c422e7b18f6f981ba7df1","datavalue":{"value":{"entity-type":"item","numeric-id":4184789,"id":"Q4184789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$E6986DC4-4C77-40D8-961D-1BE857D4907B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9598269ea56a49ba8cec40bbe6d8e68987883a91","datavalue":{"value":{"entity-type":"item","numeric-id":1155514,"id":"Q1155514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$8174C271-4D60-4659-AA23-8B663E2170F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40a4d400dc1ffd92ba8eb71a4f06727b65c37dbb","datavalue":{"value":{"entity-type":"item","numeric-id":5378742,"id":"Q5378742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$105C42B5-44C9-4C02-BE0D-A5C2A6263221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d45fa841a6a5a6e49fe7dc5b973e71a214489c6","datavalue":{"value":{"entity-type":"item","numeric-id":3896840,"id":"Q3896840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$B9B96875-6BDA-45ED-9A49-DCEDF150DCBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"495cba8abec149d5abd07c6b64a40b0c51acd899","datavalue":{"value":{"entity-type":"item","numeric-id":4393123,"id":"Q4393123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$FB8A56F7-E004-4A25-B91F-039850D8E4EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a860092cae4ad4c5ee631c0a98f0a7ee7f9c9d0","datavalue":{"value":{"entity-type":"item","numeric-id":3241581,"id":"Q3241581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$5AB0240B-454E-4B90-8E19-85B3EE738ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46a5412e4e375df998a9456d64ea1a7a8d7ffc12","datavalue":{"value":{"entity-type":"item","numeric-id":4096145,"id":"Q4096145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$B58AFA86-C6A4-4744-9943-6EFBC668A0E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebea13d153a1cd692347c4bf2c988047a9c484ab","datavalue":{"value":{"entity-type":"item","numeric-id":3882189,"id":"Q3882189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124710$E854C63F-00C3-4D15-93E4-98C107D31F6E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec3bcbdf31e4158f797a1f9d49fedcb4dd2507c7","datavalue":{"value":"https://doi.org/10.1016/s0377-2217(98)00120-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1124710$E15C0A7D-54D7-4DC6-84F5-347F06A50A82","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0468caf91f643e6465d39b728e196e3cd1273565","datavalue":{"value":"W2050997304","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124710$34845D14-9E30-45A8-96D8-B789A7B2CC60","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e1cb449b189e046106856b02f7146682e8f66e8","datavalue":{"value":{"entity-type":"item","numeric-id":2885555,"id":"Q2885555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b7dd7474a4a92f51170033064f22339dae768bf","datavalue":{"value":{"amount":"+0.8340450525283813","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":"Q1124710$062A3D6A-9E6A-4A7B-B1B8-E25C020F457E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7032954fd459bc21621ad0a9cde36e85782b68fe","datavalue":{"value":{"entity-type":"item","numeric-id":4668779,"id":"Q4668779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bccc1015fc20ede3bf0a13b6ddeaedebd5de36fc","datavalue":{"value":{"amount":"+0.8301708102226257","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":"Q1124710$F99A3F36-E205-44F5-B959-96FFD01F8D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b6890c517194a64270eb150a8e437b073af9eaf","datavalue":{"value":{"entity-type":"item","numeric-id":5883603,"id":"Q5883603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20f545bf57c7e9a8578538141dd381bc10572bd7","datavalue":{"value":{"amount":"+0.8271403312683105","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":"Q1124710$D3EB03BD-F717-42D5-91FE-A5068CBFB333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"405cb96e7ac0e501798d21a08856b9f929df9edf","datavalue":{"value":{"entity-type":"item","numeric-id":2491319,"id":"Q2491319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c025efba8d31c7d54692f6370357d6f2395031f","datavalue":{"value":{"amount":"+0.8147019147872925","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":"Q1124710$F5294BCE-B102-4E0A-BE55-A33DE433A0B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21e9be7d2a0dfbac2fceb93b30646c3d616b9ac4","datavalue":{"value":{"entity-type":"item","numeric-id":1011207,"id":"Q1011207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"594ad7e806930a5023786e49b7155c1194993d9b","datavalue":{"value":{"amount":"+0.8144694566726685","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":"Q1124710$FA024DD8-7257-40A8-A8E4-3B24D05887ED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1124710","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1124710"}}}}}