{"entities":{"Q840596":{"pageid":842444,"ns":120,"title":"Item:Q840596","lastrevid":50763896,"modified":"2026-01-15T02:19:59Z","type":"item","id":"Q840596","labels":{"en":{"language":"en","value":"An exact algorithm for the Knapsack problem with setup"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5603399"}},"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":"Q840596$C6C8AFCA-07C7-49E6-9B35-DD6005A7CDF2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"475604709c8e2628b1999331a0776c854650f409","datavalue":{"value":{"text":"An exact algorithm for the Knapsack problem with setup","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q840596$2941FD21-5DFC-4341-90F0-1A9621F54AC7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1cfbd01285a70404af39b1a0947a5177dd1dd826","datavalue":{"value":"1169.90485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840596$4B448464-33DE-48E2-AB10-F1876B0DCF34","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d3f75a42e42cd80bfac9f7038451d303f8b5faf","datavalue":{"value":"10.1504/IJOR.2009.025197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840596$8D9B2516-B004-4F2F-A3A9-63394A320EDA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06c9a67677b3ed13c0557317b0f933ca167e7731","datavalue":{"value":{"entity-type":"item","numeric-id":840594,"id":"Q840594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q840596$A9435884-5E1D-4340-ABD6-9CEC5DF963D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a77f3e7f653a008ecd18602892eb1d08f55640f4","datavalue":{"value":{"entity-type":"item","numeric-id":840595,"id":"Q840595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q840596$56CB5B87-89A9-407F-A339-CE407670EC7E","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":"Q840596$A42C0E1C-07EA-4CE6-A377-F98604FC0E79","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":"Q840596$C162B3F9-F93F-4C11-A80D-2986559BA54C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9e776fe08cc13a2fa3e7c25ce2f24a5653fd2e6","datavalue":{"value":"Summary: In this paper, we study a \\(0-1\\) Knapsack problem with setup (KPS). One set of \\(0-1\\) variables represents a family setup and serves as an upper bound (UB) on another set of \\(0-1\\) variables representing production of a job in a family. We present a branch-and-bound algorithm to find an optimal solution to KPS. The algorithm uses a two-stage branching strategy and chooses the next candidate problem to be explored in a non-traditional way. We verify the efficiency of the algorithm through computational testing. This is the first time that an exact algorithm is applied to a KPS with 10,000 integer variables. Computational experiments show that the algorithm is especially effective when objective and constraint coefficients are uncorrelated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q840596$F21EF7EF-14D4-48FB-A9E7-079E3ABA41E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840596$19A46796-2CB5-4C50-BD35-7AF2D4328A8E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"75b42bfc9df04817a13db8687971f1c5dd4d15a5","datavalue":{"value":"5603399","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q840596$4017691F-F966-44D8-8D20-7A3344547025","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0422c0032d8a2889d42dc691fc1ef8ac885917f7","datavalue":{"value":"Knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q840596$1B00F37F-CEAC-4213-90A5-C8EA6D3EDD47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2428172f28a6233f9f126d425a5fed80d6391f0","datavalue":{"value":"setup","type":"string"},"datatype":"string"},"type":"statement","id":"Q840596$EA393CA5-13D5-4754-B6A4-5CB3C8496351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q840596$5182103E-6560-42A8-9770-81D3BEC94FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q840596$4B35A5B3-DE5F-45AC-AB18-4CEAF1F8DA6E","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":"Q840596$9ED0C10A-9619-44DC-9C6D-3ACFFC0641F6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08deb0ea6621c20c51461b99fd12487752d92282","datavalue":{"value":{"entity-type":"item","numeric-id":1652189,"id":"Q1652189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f3cc1ee1884936e0f3c4afa650e9d325c425485","datavalue":{"value":{"amount":"+0.8745868802070618","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":"Q840596$08F5E255-DB8C-4158-A5EF-24EDBE61812E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1cb6f5af1f74ece24460d6d75c2f43664d9b430","datavalue":{"value":{"entity-type":"item","numeric-id":4313817,"id":"Q4313817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"daf5dad65517abcff9bb2c9024d684d8851c3ae0","datavalue":{"value":{"amount":"+0.8699551820755005","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":"Q840596$21866B94-B039-449E-8F86-6FCDF8FCB084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b00ee9e240b21732ee5a20d27e25eed56a8cb28","datavalue":{"value":{"entity-type":"item","numeric-id":342065,"id":"Q342065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97c2dc193d3cf4d51e91bc3f5c916bf882daaef8","datavalue":{"value":{"amount":"+0.8578184247016907","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":"Q840596$D4ED852C-5EE5-4BCE-A177-9349703DC813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0788eb9c922ce47d4e345420c15fc15b59ce755","datavalue":{"value":{"entity-type":"item","numeric-id":1652523,"id":"Q1652523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a57ead7f3594c92fa2311436d3a1e787884ca262","datavalue":{"value":{"amount":"+0.8445077538490295","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":"Q840596$04357495-B622-4CA3-B48A-4B232A78E1BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63924abf92f1325301764d2fa8d1f354a8931d84","datavalue":{"value":{"entity-type":"item","numeric-id":3116647,"id":"Q3116647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"872a5aa2b7647b97d749b3f837fdf7f60c403dda","datavalue":{"value":{"amount":"+0.8410822153091431","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":"Q840596$39DCCBD7-86D5-4B4A-85B2-3297C8F91D2E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:840596","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:840596"}}}}}