{"entities":{"Q658556":{"pageid":660405,"ns":120,"title":"Item:Q658556","lastrevid":63389406,"modified":"2026-04-11T12:32:12Z","type":"item","id":"Q658556","labels":{"en":{"language":"en","value":"Global optimality conditions and optimization methods for quadratic knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5996880"}},"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":"Q658556$33E045D5-6E45-48E4-B966-977B440F3A0D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b2f68b132c7feaa12d9965bd319b8f863941f2c5","datavalue":{"value":{"text":"Global optimality conditions and optimization methods for quadratic knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q658556$1586FEBC-1EC8-498F-A456-9E744E0E9F1E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64fa6d6033eb22174413bb0a79d55d87a9755d1b","datavalue":{"value":"1237.90214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$E6ABE9A8-A8F0-4600-9FE7-ED33CA1BE20E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03146bb8e17b3d6cc14817a371f8c48ba30cf452","datavalue":{"value":{"entity-type":"item","numeric-id":624377,"id":"Q624377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$50C42A50-568E-46FD-BDBE-063F2A53C593","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a3c8bf4d8569c126380a9fc42f55609089e776fb","datavalue":{"value":{"entity-type":"item","numeric-id":82026,"id":"Q82026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$B382D442-A748-443B-A80B-526B9BA88435","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1d825051870bac730440e37fabd5e37e0762e48d","datavalue":{"value":{"time":"+2012-01-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q658556$597B40B9-79FD-4F47-9645-2E7869ECC2CA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fc3f2107012e4d0e06266db93b03a1215715db1a","datavalue":{"value":"The quadratic knapsack problem (QKP) maximizes a quadratic objective function subject to a binary and linear capacity constraint. The classic knapsack problem (CKP) is a special kind of QKP with no cross terms for the objective function, and the supermodular knapsack problem (SKP) is a special kind of QKP with nonnegative cross terms for the objective function. Due to the simple structure and challenging difficulty of QKP, it has been studied intensively during the last two decades. There are only a few methods available to solve QKP with some negative cross terms, namely LP relaxations, semidefinite relaxations, and some dynamic programming algorithms.  This paper first presents some global optimality conditions for QKP, which include independent necessary conditions and sufficient conditions. Then a local optimization method for QKP is developed and the algorithm is presented using the necessary global optimality conditions. The number of iterations the algorithm requires to reach a local maximizer of the problem QKP is also derived. Finally, a global optimization method for QKP is proposed based on the sufficient global optimality condition, the local optimization method and an auxiliary function. The exact algorithm with some analysis of its functionality is also given.  The paper concludes with several numerical examples to illustrate the efficiency of the presented optimization methods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q658556$5BA4950A-46CA-467B-A2D3-569FF042B33E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$75D97D11-16F1-484B-8916-AA628FDA894C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$4B2F27B8-1BA3-43A6-A603-BB2199B9EFDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed10a41ec587cb61dc683f25ef4b3e827c7fee2f","datavalue":{"value":"90C26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$C2FCA964-332D-4F8B-9877-14ECFCB27EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"15f4e876d21d5111ed972346cf4b55d9dc89f6a2","datavalue":{"value":"90C46","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$8AF36274-0FAA-46FC-8542-F29D7FD8D568","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e8494749e07c93c803251ea3b61801ef5747844d","datavalue":{"value":"5996880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$23152571-B0E7-460A-8985-6D365C29FF7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1511138fe0b5f3a5cc6f283e9a99ad03823cc02","datavalue":{"value":"quadratic knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q658556$40038926-07FC-4D16-B43F-569D8E98F312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3830311d0e0d8c281cf875a2eeec624679619bff","datavalue":{"value":"global optimality conditions","type":"string"},"datatype":"string"},"type":"statement","id":"Q658556$1BAC06A8-3C1C-434A-8A22-5AED5BAF4536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c56e66924bb370940bda29cf81801fac17535ea","datavalue":{"value":"local optimization method","type":"string"},"datatype":"string"},"type":"statement","id":"Q658556$0D1D7336-FFBF-4B96-877B-E07901DEB290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f113fda16f8403708ac7b27c2a5601d179e53316","datavalue":{"value":"global optimization method","type":"string"},"datatype":"string"},"type":"statement","id":"Q658556$71191ABB-1C21-4175-B1DA-E8695726F538","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":"Q658556$A041D370-7537-4007-AC87-0B64C6525195","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":"Q658556$D4C26AA9-FF54-416D-A34D-2CDCFF807860","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6d3343f7d0fe70919cd1c50880130df7d20b73fb","datavalue":{"value":"https://doi.org/10.1007/s10957-011-9885-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q658556$DE47614F-2712-47EA-B300-396554C11D5D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17cb9e75bfbe8bb01187bfba4084e7f6b6613814","datavalue":{"value":"W1973286416","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$B7F9018B-83D5-4A37-9495-C0DA6FF957C1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3bf29cd5adde089122ba16e4d9f3b5b52150c2c3","datavalue":{"value":"Q56050296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$C1786A9B-334D-4871-A883-D1D047B173C1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"81738ef4dc913499bf4e81070a1ea9ab3ec63e17","datavalue":{"value":{"entity-type":"item","numeric-id":3912370,"id":"Q3912370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$FA2E17D1-9170-4B6E-B3A8-A49AEF1EC713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9ff15631c44ccf26d9f412a66e82f7bcf3f094e","datavalue":{"value":{"entity-type":"item","numeric-id":875597,"id":"Q875597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$D472A8DF-6D8A-4562-9F41-F5FC5191AC17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5d2ff8ca55c71a00eb97ded234e95c181b7889c","datavalue":{"value":{"entity-type":"item","numeric-id":5603745,"id":"Q5603745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$2D0500BF-1457-4930-9D2D-A0CEDFE81572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26051ddeae51a13c81984b3fe78232a0e5fa05b7","datavalue":{"value":{"entity-type":"item","numeric-id":1321669,"id":"Q1321669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$E929B6B5-1862-46B4-9C4B-454831E13BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c728f00926759a14e47cf3124c183d24938cf7fe","datavalue":{"value":{"entity-type":"item","numeric-id":1806683,"id":"Q1806683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$46BC4577-F3B8-4A86-B74A-DDB70D6A260F","rank":"normal"},{"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":"Q658556$1B0FEF68-F1E6-408A-9DF3-27372159A8AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0057790c66f186d3db4d9b87c984eedd48770c34","datavalue":{"value":{"entity-type":"item","numeric-id":4247440,"id":"Q4247440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$98BBD7EA-9B85-46B6-8913-C14D50CA9C6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f7044f3e97c60e8e88ea678cbe40168f7f5d432","datavalue":{"value":{"entity-type":"item","numeric-id":703909,"id":"Q703909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$2328D6C8-A87B-448F-916D-90C8A4D80CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25d5db05e285e3c12cd17d22076b75bd29dbf173","datavalue":{"value":{"entity-type":"item","numeric-id":1824552,"id":"Q1824552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$1C77F678-107F-4842-9993-A1DE03954ED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d7c3ef515236f155a2b780201bea00c026b19ba","datavalue":{"value":{"entity-type":"item","numeric-id":4372880,"id":"Q4372880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$509B28B0-6ADD-4E80-A3A4-5E7130AEC5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c6608bcad6488a24c4697af5baa124897418e0","datavalue":{"value":{"entity-type":"item","numeric-id":1268265,"id":"Q1268265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$A5C224B6-0C8E-470B-A1EE-78514A2B752A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7af6b57f75317319316b831d679b15960c90770f","datavalue":{"value":{"entity-type":"item","numeric-id":4427369,"id":"Q4427369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$5E0487FB-1478-4600-ACA1-83B5D9435DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc3cb39119977786399c49a58de619bec2784b63","datavalue":{"value":{"entity-type":"item","numeric-id":1268263,"id":"Q1268263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$A9C82427-C525-46BE-960F-DE31EF588291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f8dd2502b79677c1c4b9bcd1e0a1e7f078b436","datavalue":{"value":{"entity-type":"item","numeric-id":1866980,"id":"Q1866980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$D8D49E65-6A83-417D-9323-F690097BCCA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af188edc1e246618e496bd5ebc06f040b624869f","datavalue":{"value":{"entity-type":"item","numeric-id":2706322,"id":"Q2706322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$80ADAFF8-C6BC-4092-93C1-1D5854C738E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ee2a64ff99c363a668c5c2241a36122c8b01da9","datavalue":{"value":{"entity-type":"item","numeric-id":2433932,"id":"Q2433932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$69D8AD06-ECCE-4B89-BB38-A3CC13AEA91F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c94f0d8dd90c7e6b2acee459fb04ea861e6ede66","datavalue":{"value":{"entity-type":"item","numeric-id":702386,"id":"Q702386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$94086D87-A4E7-4982-94A0-8F2A59988ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f552ab6eb0211de1f21ae9660e0f5827bb0a337b","datavalue":{"value":{"entity-type":"item","numeric-id":1304172,"id":"Q1304172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q658556$054B57FD-7CC8-4CCF-BE85-1280E76DB6AB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"83e5a9d176b1c2db26162e7a6b042192bd7077d1","datavalue":{"value":"10.1007/S10957-011-9885-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q658556$43EF4296-3E3D-4676-A01F-0BD38B0CF7D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19c07d925ea382a5f545a9224f80e9236288ab30","datavalue":{"value":{"entity-type":"item","numeric-id":2835673,"id":"Q2835673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43202796cd6bf2b1043a49bcd48a48fe0a804c72","datavalue":{"value":{"amount":"+0.821337878704071","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":"Q658556$5FFA220A-6574-40C7-9744-05B75B6BF3DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcd4b064c7f8799f8de4d75ff398c0391bdfe556","datavalue":{"value":{"entity-type":"item","numeric-id":806968,"id":"Q806968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d97f61ec578e71b033ecf552f5c1b2f02e63c075","datavalue":{"value":{"amount":"+0.7993231415748596","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":"Q658556$5538D475-7717-4D3A-AFFB-0E4CEC0C1BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcfcd56e5483582a245a309395b48228d1df2454","datavalue":{"value":{"entity-type":"item","numeric-id":4427369,"id":"Q4427369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f2aad7370475f7ed27ee67a788270d6e3c90c0a","datavalue":{"value":{"amount":"+0.79140305519104","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":"Q658556$9F8053F0-1812-4643-AE2D-7BE8DC036996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b570a8921df0a4dec7d5f8dac103a78c9fac1ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3059316,"id":"Q3059316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d74f113810f2638ae32ea1405f32d43b50a841bb","datavalue":{"value":{"amount":"+0.7909371852874756","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":"Q658556$2DE26DBC-0551-443A-95D5-2FADCAFBCDA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36032b4cd05bc0dee4e09f04d2a90be4559009a2","datavalue":{"value":{"entity-type":"item","numeric-id":422852,"id":"Q422852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c76d91bf010409ccb4d7a36d3b1d6ccb7205e17e","datavalue":{"value":{"amount":"+0.7897194027900696","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":"Q658556$DCE49CB0-1605-49F9-8443-E373E3F1C64D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Global optimality conditions and optimization methods for quadratic knapsack problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Global_optimality_conditions_and_optimization_methods_for_quadratic_knapsack_problems"}}}}}