{"entities":{"Q840573":{"pageid":842421,"ns":120,"title":"Item:Q840573","lastrevid":50763839,"modified":"2026-01-15T02:19:57Z","type":"item","id":"Q840573","labels":{"en":{"language":"en","value":"Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5603389"}},"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":"Q840573$0302F763-D6F1-4975-B20A-925831BFB762","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a114fe9386f43792b28dd5122215698b8709b15","datavalue":{"value":{"text":"Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q840573$946CCA5E-CF80-4510-9A79-981195375A91","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"98fae040c0f68b441044598dea1054d9a853b59e","datavalue":{"value":"1169.90484","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840573$AC5FAA6F-4C65-48EF-BA02-924D85DA9CE7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"244023292b5b475c46035e8f0aebfd9917639329","datavalue":{"value":"10.1504/IJOR.2009.024531","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840573$E26C3421-0CF0-472E-A02B-D28DDFD57F21","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c6a112a277711a541209b5a2cb1b852b5f83a478","datavalue":{"value":{"entity-type":"item","numeric-id":840572,"id":"Q840572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q840573$6547CD68-76E8-45E8-860F-A5A8E53002C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97c9edf655b7856699523779b519f21abd1c7c36","datavalue":{"value":{"entity-type":"item","numeric-id":174583,"id":"Q174583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q840573$CA4219BB-F156-4C3C-A08E-A9250F04F62F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q840573$BCC53B63-8801-4B6A-9834-CF476C2C02FB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"60de08cdec9dc56d163af99afabe1a4d652ad0ba","datavalue":{"value":{"time":"+2009-09-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q840573$D34CF811-891E-4A2D-BDCA-5A38FE93BAD6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cb1e797adae5c82dd74da2a56ef9bbf944649ba5","datavalue":{"value":"Summary: In this paper, we propose three versions of an algorithm for approximately solving large-scale \\textit{multiple-choice multi-dimensional knapsack problems} (MMKP). First, an adaptation of the local branching is proposed. Second, a hybrid solution procedure is presented that is based on two complementary solution procedures: a local branching which cooperates with a column generation solution procedure. Third and last, an augmented algorithm of the last hybrid algorithm is developed. It can also be viewed as a special truncated branch-and-bound in which the first hybrid algorithm is applied to a subset of elite nodes generated according to some variables/constraint branchings. The proposed methods are analysed computationally on a set of instances from the literature and compared to the results provided by other algorithms therein. Encouraging results have been obtained.","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$EF232AE6-EFCE-4C2C-8854-1D08367728CF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840573$17EEB77A-FC8F-48DE-B8A5-0890872BFDA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840573$8E8B263A-D026-4254-88C6-9D71990E93E6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"13ff0beb4a47fb562443cec16e8bd0125e4496b3","datavalue":{"value":"5603389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840573$5B051B4B-9B38-409F-AAD8-D3A853BD4A77","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$DBAE90A6-8DAA-43E5-9625-6A69FAF0A14C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2401d939235d16408479f759cf86bb78a50fdb4","datavalue":{"value":"column generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$D02A0D81-BA17-42D6-99DD-941A918E9E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$5E3969F5-8C85-4B27-BFAE-4F0C3B727790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$A527D770-37FD-4D67-9C38-3CEE84DC33E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ed91c03d85e935a70b5045311a3f3181f1ab55a","datavalue":{"value":"local branching","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$D526CBB5-17BD-4774-9FFA-C81C472EAD6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1d9324f9aeeea351a8db73f8cf20002060b26de","datavalue":{"value":"optimisation","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$5DE7138F-3016-443A-BB1F-81F86E80BF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1208c0ddd4492fcd0f44407f250d56f89d150fb","datavalue":{"value":"multiple choice","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$A080E6B4-86F6-46BD-9A5F-A37E89DA46EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"deac56ddc17cee73737f3f85f189c583ac04b4dc","datavalue":{"value":"hybrid algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q840573$356D50E3-1D7C-4C20-B626-58D654F72998","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":"Q840573$4C927FB8-E772-4FBA-92D0-137A3C34041A","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":"Q840573$2460CFB8-5018-41F6-A20E-DA4337C07DD4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a153f528cbc5956b5b053d296bb7d4f4c19b727b","datavalue":{"value":"https://doi.org/10.1504/ijor.2009.024531","type":"string"},"datatype":"url"},"type":"statement","id":"Q840573$73EFCEC9-2115-4840-8692-F77A1EC50B33","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d59e0db3386b5f3324cfb405fda4ab47148c76f5","datavalue":{"value":"W3023784225","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840573$0A055350-3836-4AAA-8F97-4C80E391FD0D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e636d1de9963c5fe82075d4b21a407eb0cfc841","datavalue":{"value":{"entity-type":"item","numeric-id":969718,"id":"Q969718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a1dd8d1fee9717faedef431ce999c8b78e985a3","datavalue":{"value":{"amount":"+0.8637934923171997","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":"Q840573$ED4CFA5F-31F1-4A0F-9644-E13EEEEA19CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72ac76f91ead2004b358c28b1454a6550121f86c","datavalue":{"value":{"entity-type":"item","numeric-id":4678202,"id":"Q4678202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25b5cba2b1836564e90a350e4bb4e11ae8c27957","datavalue":{"value":{"amount":"+0.8589122891426086","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":"Q840573$178D4736-9C32-41CA-8AD3-C11F789811C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cf5bded6e37f204876fd15b4a652c1da840779d","datavalue":{"value":{"entity-type":"item","numeric-id":1894383,"id":"Q1894383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c721f036258ede581725db8315ef5004dd26378","datavalue":{"value":{"amount":"+0.8494687080383301","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":"Q840573$98CAB247-661A-4340-9E04-450228CD7428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17d84a05996b61d6c56251a39ca9d95b597ffc21","datavalue":{"value":{"entity-type":"item","numeric-id":3571520,"id":"Q3571520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4534c019bcc83440076e0d2d7354d0be893b9a16","datavalue":{"value":{"amount":"+0.8422856330871582","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":"Q840573$595DFE8B-E50D-497B-8943-ED9E96C15CE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5ecb52ae0e6affc16c4c4a6bc13e50361b016fa","datavalue":{"value":{"entity-type":"item","numeric-id":2467571,"id":"Q2467571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cca9e2204e905911116737c3ebcb38c9dd1c9d2f","datavalue":{"value":{"amount":"+0.8416191935539246","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":"Q840573$6C512A17-6014-4231-B742-D5C1F34307E6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:840573","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:840573"}}}}}