{"entities":{"Q1096544":{"pageid":1107296,"ns":120,"title":"Item:Q1096544","lastrevid":49124869,"modified":"2026-01-06T15:28:55Z","type":"item","id":"Q1096544","labels":{"en":{"language":"en","value":"Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4031407"}},"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":"Q1096544$3A3D1A78-5E49-4D5E-8B08-BE8750651414","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a7271e9ebd4d2eb2576b4124d1e4ca7ccad1339f","datavalue":{"value":{"text":"Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1096544$CF881ADE-11D6-4E73-9EFC-1E7A6BCD0426","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d974f33ebabb4c02b6e41d15a344962ce283d689","datavalue":{"value":"0633.90060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096544$945E002B-A5E0-424C-80EC-8FD701AF3F63","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2025912e44a778adc52ac874236ae6aa6a4a6aad","datavalue":{"value":"10.1016/0166-218X(87)90015-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096544$969095C1-F433-4190-9209-03F90A477E29","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ed33963a50bf8211f69efc736b14559d62e0ecf","datavalue":{"value":{"entity-type":"item","numeric-id":1096542,"id":"Q1096542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$0E930994-47D2-4C33-8926-78F54296AF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4b382eb2e3a068a862d5096a039ff6b343f2c70","datavalue":{"value":{"entity-type":"item","numeric-id":1096543,"id":"Q1096543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$782DE5A8-DE7B-4694-9B73-C0236F11A646","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$E80944FD-F08F-44AC-B9C5-B0D07F1D0A39","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1096544$90EC7734-2A7A-422E-8A2C-6DB8C56DE299","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b9a4439213c73899065ade85dfa9c5aa4a1d86e7","datavalue":{"value":"The problem (P) addressed here is a special set partitioning problem with two additional non-trivial constraints. A Lagrangean Relaxation \\((LR_ u)\\) is proposed to provide a lower bound to the optimal solution to this problem. This Lagrangean relaxation is accomplished by a subgradient optimization procedure which solves at each iteration a special 0-1 knapsack problem (KP-k). We give two procedures to solve (KP-k), namely an implicit enumeration algorithm and a column generation method. The approach is promising for it provides feasible integer solutions to the side constraints that will hopefully be optimal to most of the instances of the problem (P). Properties of the feasible solutions to (KP-k) are highlighted and it is shown that the linear programming relaxation to this problem has a worst case time bound of order \\(O(n^ 3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$24CCE26C-5C5D-4FE3-B11C-088B62D93F02","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096544$A67160E6-DCB0-414F-9D2C-7E737AD7A093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096544$E82E6BEF-E460-4064-9403-17A23BBA28B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096544$53F0700C-5731-4AEA-BBCE-5AD9305EC6EA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bba92863290738764a5b067e1818fdbe8d653900","datavalue":{"value":"4031407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096544$00DDD695-CF4F-4AA3-ACD0-25CD29C425AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52de5883751daf770e52b335cde888ca59e1a57c","datavalue":{"value":"set partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$75652265-DE88-41A1-B1B4-76EE8F90BB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cbb28502752f9287d22af6eb68f71f9164c90da","datavalue":{"value":"two additional non-trivial constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$6371E209-DE40-4093-916C-616326E0949E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44e33be0f6bdcecd082a97d65b90b8ac4e91afcd","datavalue":{"value":"Lagrangean Relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$57BC3EE6-80E2-4B9C-BD20-717B1A7A9B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$AC57778D-AAD8-4726-805F-B49D36AFB612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311c918aa73c0095f25f775f111e8abd535d104e","datavalue":{"value":"optimal solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$1BD458A7-FA0D-4821-B21F-9111A6155B51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20d1a14fb28c3ab35e4a0798b5165dd5bedd2386","datavalue":{"value":"subgradient optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$CC4FB21A-2E9C-44AE-B898-8DE474B1026B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2401d939235d16408479f759cf86bb78a50fdb4","datavalue":{"value":"column generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096544$0EF67121-9101-470B-B74F-EB98324D9CDE","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":"Q1096544$6D4D64BF-C437-4D49-98E9-B85BDB7E9AF6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6537454b90786e832c3e223050ba3e6d63e5c1","datavalue":{"value":{"entity-type":"item","numeric-id":4132008,"id":"Q4132008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$C69B9C5A-981C-44D6-BBC7-51F369583E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67729b1304819cd23b80be0e5e92a17db360b2d","datavalue":{"value":{"entity-type":"item","numeric-id":4117604,"id":"Q4117604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$BB548C35-B8EA-4B9F-A839-72758F00A228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da50b75aee7f8ca6410c34ac9ccf11c66442d818","datavalue":{"value":{"entity-type":"item","numeric-id":3735467,"id":"Q3735467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$495CF86D-4104-4804-B27E-0DCF5B9EA9E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"624c591121cb6f9e7c8602b2d2d35fd7a7f74367","datavalue":{"value":{"entity-type":"item","numeric-id":3813600,"id":"Q3813600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$8318F3B8-6E7A-4088-8CE8-F9AAA8D25843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"083d97e730faf90a4132402a3f045bdbf076bc3c","datavalue":{"value":{"entity-type":"item","numeric-id":3919449,"id":"Q3919449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$DAE6881A-0BD1-4EC8-A373-B7FF88440EEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36ebf6e68a3198b033e9828224a4d871e5c811d9","datavalue":{"value":{"entity-type":"item","numeric-id":4740330,"id":"Q4740330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$BE56A1DC-CC3A-4215-91CE-0CB7818B00A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f57cb52d5b46d9b84e5c5fdecf79231c1f4f0138","datavalue":{"value":{"entity-type":"item","numeric-id":4178782,"id":"Q4178782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$73368B13-4C7F-4679-83AA-D54A8000E437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ef186d04700ec05e2c80648ed2e4ff1dd1c87cc","datavalue":{"value":{"entity-type":"item","numeric-id":3854926,"id":"Q3854926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$A2296CB9-9B7B-49DE-8C64-A3C6FBCD7A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8634671064abab94a7b8dbe7f85bfc42274b7db2","datavalue":{"value":{"entity-type":"item","numeric-id":4770776,"id":"Q4770776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$E0D9E0B9-6E3B-4A91-8440-820A6A7433C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b90ce504ed648b1fc2f51b59a5d15ef6f796ea6","datavalue":{"value":{"entity-type":"item","numeric-id":1168894,"id":"Q1168894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$39923167-DA7F-48A2-BB72-4ECFD583DCA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a49c45cfeee592259d7dad085948a609b194d064","datavalue":{"value":{"entity-type":"item","numeric-id":5630824,"id":"Q5630824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$A267D849-B50C-4FBF-B64D-9F33BF1DB8E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"442c9a80830d9f9b701ad4523cb3fdb9721d7cc1","datavalue":{"value":{"entity-type":"item","numeric-id":3042878,"id":"Q3042878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$91B724A3-CC7C-4C1F-9A01-8B7E566A063F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5bf9ddb289e11e90183556cbf7ae776c17c9386","datavalue":{"value":{"entity-type":"item","numeric-id":5338603,"id":"Q5338603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$2D1BDE0B-E418-42BA-8FD3-39946026354F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c306ced799281c6c945690af18a1c480f7ce9711","datavalue":{"value":{"entity-type":"item","numeric-id":4060729,"id":"Q4060729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$5ACB64F6-4EB5-4C4D-9801-E0D43C48C8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53270a197dc74dec5db368885ae5da2d9b50fbb5","datavalue":{"value":{"entity-type":"item","numeric-id":1253450,"id":"Q1253450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$866BA7DA-0743-479A-911D-DF463FBB1BA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6329aa3f53b0007d7c30145137b42eaa70d002d9","datavalue":{"value":{"entity-type":"item","numeric-id":5588250,"id":"Q5588250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096544$2C2A26B7-0CA8-4919-96C9-A88FDB7364C7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6c9173318532a78c33d4439e915998dc9edd1434","datavalue":{"value":"https://doi.org/10.1016/0166-218x(87)90015-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1096544$7072D8BF-CE7A-462F-B094-4551A4553A3F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5381a306b0135673bdbea6e7773acf4f1e99aa1","datavalue":{"value":"W2060879564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096544$613A45E8-BB5E-4C58-A89B-F3C16C9CA2FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96b397b210d34a7cb3e3fdba21e28968dbd9602b","datavalue":{"value":{"entity-type":"item","numeric-id":1876461,"id":"Q1876461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a624780c59864c4ab35ff978c69099b3fddb9ee4","datavalue":{"value":{"amount":"+0.7793732285499573","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":"Q1096544$AFE887FE-CDBB-4815-8D16-5A380C2659B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec310743d52c0f92ed3d58ecfbb706e2a6522ba9","datavalue":{"value":{"entity-type":"item","numeric-id":3786281,"id":"Q3786281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81b8601472aa57a738da83991f37b802d0938a32","datavalue":{"value":{"amount":"+0.7792643308639526","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":"Q1096544$AA11A416-F183-41CA-822B-60E6DE1BA02D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fa125ba0a5815fa62facfd8dd149dc2c7ca91b9","datavalue":{"value":{"entity-type":"item","numeric-id":4026988,"id":"Q4026988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ef6954f6a6efa4014096666a7731f05ad116f7f","datavalue":{"value":{"amount":"+0.775253415107727","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":"Q1096544$FC847A90-D9C1-4261-8421-546B5614F8CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa55fd03f1737cb76e0245e1973130a2a7cb90d4","datavalue":{"value":{"entity-type":"item","numeric-id":1922639,"id":"Q1922639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"802d5fe0d20f29350f29bc46b51c83180f4a9aef","datavalue":{"value":{"amount":"+0.7750806212425232","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":"Q1096544$EACD8568-A250-4D76-9B48-DE82ACE51F18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a963856776116bed2c872e4aaf0afcdbfcc39a4c","datavalue":{"value":{"entity-type":"item","numeric-id":922948,"id":"Q922948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4887e09c0db0c803bee9323613bd4a09479a97cb","datavalue":{"value":{"amount":"+0.771587610244751","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":"Q1096544$685D1123-844A-4A96-BD28-C596FBE54F5C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1096544","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1096544"}}}}}