{"entities":{"Q1088908":{"pageid":1099660,"ns":120,"title":"Item:Q1088908","lastrevid":49058992,"modified":"2026-01-06T13:11:02Z","type":"item","id":"Q1088908","labels":{"en":{"language":"en","value":"A new Lagrangian relaxation approach to the generalized assignment problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4001875"}},"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":"Q1088908$43E1E00F-BCAC-417B-9ED9-78025AD73DBD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c3a28e9f430730d351db47151be7e98f3e2d0217","datavalue":{"value":{"text":"A new Lagrangian relaxation approach to the generalized assignment problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1088908$CDC45600-DCAA-4594-8951-0291366F3622","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c31f80a234c627a62168b856bcdfb1fd70ceaca","datavalue":{"value":"0617.90068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088908$A68EE288-B22D-4431-8879-83704F12F52A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2f971dda492c57f43e528e897750e7d365d08a2f","datavalue":{"value":"10.1016/0377-2217(86)90328-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088908$46E76FAB-A7FE-47E4-B24A-3243AB554676","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"572cfa6bd14d8c78d0c95cceb95bb666d63da036","datavalue":{"value":{"entity-type":"item","numeric-id":1088907,"id":"Q1088907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$00F08D26-A46B-426C-BD67-FF37846F4A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e97c50d206f3c919c30ae267c4bd966749f39cb7","datavalue":{"value":{"entity-type":"item","numeric-id":684334,"id":"Q684334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$40E600D2-ACAC-4F1B-8678-734986497FE7","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":"Q1088908$F7CBFEB4-7A26-4675-8308-312557E2020E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1088908$E095C51B-DDB5-475F-A429-202373A42ED9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e29595e225b8644881bd4dcabe697d3b09414282","datavalue":{"value":"We present a new Lagrangian relaxation approach to the generalized assignment problem (GAP). The new approach is based on a reformulation of GAP into an equivalent problem, which is then relaxed by traditional Lagrangian relaxation techniques. The reformulation is created by introducing a set of auxiliary variables and a number of coupling constraints. By relaxing the coupling constraints we get subproblems where both types of constraint structures present in the GAP are active. The lower bound from the Lagrangian dual of this approach is shown to be at least as strong as that from the best of the traditional Lagrangian relaxation approaches. An important feature is also the possibility of generating upper bounds quite easily.    The new approach has been tested on 10 problems of size \\(m=4\\), \\(n=25\\), i.e. 100 0/1-variables, and the results have been compared with the traditional approaches.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088908$3D39191B-B449-4F6F-AA99-99047B8A9F81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088908$1EB678D1-7738-4D02-A19F-214BFBB157F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088908$C9B8E027-7582-401A-8764-85492DC7799C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088908$C2C216A0-DD9E-458D-A496-E82FCE2FFF66","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e66efbd8b7958ca16eff2c696797de8a5610a05","datavalue":{"value":"4001875","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088908$C3FC3DF7-A531-4B92-900A-CE81674216CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a59e0c1eb51c50ee8b2be5656da8a2be878f5f1","datavalue":{"value":"Lagrangian relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088908$DD0A69B7-5CDA-4F64-88B1-A8AB65C39012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23953ada61d19fd5a9f7a3b6d73d811afa58f5f1","datavalue":{"value":"generalized assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088908$E1E2167A-8405-4D8C-A600-4B215ADA7697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4289e523c968275011f07b0ddb3e2dca16831f0b","datavalue":{"value":"auxiliary variables","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088908$B5DACBE0-95B1-417F-B1AC-1E805FE6B6B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d18188480c9b439bfc1e6ab032e57e066e76537c","datavalue":{"value":"coupling constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088908$22EE77F9-910A-4E84-BE5D-4DB166931068","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":"Q1088908$13517D29-5CBB-48A7-B1FE-98B7FCAC1478","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4004ea7345784eb8eb719673c65fd452d6647c44","datavalue":{"value":"https://doi.org/10.1016/0377-2217(86)90328-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1088908$096363EF-4765-47C6-9BC2-90F667E219C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"60c61ef255984f71a1b97406c0118f6cb8afff81","datavalue":{"value":"W2033791397","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088908$75A63E64-2412-4CD8-A375-127EF31F8FF2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"79eb09e52de63ab7294693c37224e40a96045fbc","datavalue":{"value":{"entity-type":"item","numeric-id":4152351,"id":"Q4152351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$CE344495-FDF9-4C01-B463-5F2C9CF2DF8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48612397ea5022418a28cc688db30cf74ebe8f6e","datavalue":{"value":{"entity-type":"item","numeric-id":3221756,"id":"Q3221756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$09E41A1F-F380-4201-A74E-D1E3BD5A8C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c471fdc9efb2952a459caec271bd366298d480f","datavalue":{"value":{"entity-type":"item","numeric-id":3315277,"id":"Q3315277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$E79250BC-AD51-4C9F-A229-064AFDA2EF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"613599edc92e38a46f3320b4b5514096fcd17234","datavalue":{"value":{"entity-type":"item","numeric-id":3850361,"id":"Q3850361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$8D69A465-6D05-4EF3-8873-6BCB86A5E42A","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":"Q1088908$A3709D14-C434-464C-8F36-7C0ABC40D46C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"212f07c415ef8012848f935f837361eec248c785","datavalue":{"value":{"entity-type":"item","numeric-id":3030567,"id":"Q3030567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$F5C48C3A-648F-4AF2-8AF3-F16CFB9FDCCF","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":"Q1088908$87DE271E-114B-49F7-B87D-046AACA08B32","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":"Q1088908$1D228221-D093-4DD8-AD12-560364BCDDCD","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":"Q1088908$33D85643-F49B-45D0-98F5-8C9BE9CBE1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a555ccdb6802250e31bbd6d3f3290f109249d9f1","datavalue":{"value":{"entity-type":"item","numeric-id":1088908,"id":"Q1088908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$336FB564-A9B3-4E67-8060-EF348878D1F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"768f318bf6c49337dca965d936f82bf20453c0b8","datavalue":{"value":{"entity-type":"item","numeric-id":3854930,"id":"Q3854930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$936B57F4-6688-46BF-9184-0B34D74B203F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51c22de9b1dd7defd654d9d1c6890d9b955add8a","datavalue":{"value":{"entity-type":"item","numeric-id":3901302,"id":"Q3901302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$F796AAF8-3067-48B0-8A0C-0CA45D1E8B9D","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":"Q1088908$3E7031C2-8AE1-4939-BE8E-404D59193407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2aa4eeac790205c4037ea67c80426826ddde338","datavalue":{"value":{"entity-type":"item","numeric-id":5638112,"id":"Q5638112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$564C6F63-BF1F-4191-83D8-ACB6597E1D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02679cf0bd55c6ca379473f90160a6bb638f1f28","datavalue":{"value":{"entity-type":"item","numeric-id":4066849,"id":"Q4066849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$1F6DE48C-FB32-48AE-96DA-3E90093959B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78873d31b1c7a4d703dc27b5e2ee42e3112bde06","datavalue":{"value":{"entity-type":"item","numeric-id":4082544,"id":"Q4082544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$A075364A-4550-4D06-9053-39EE04EDDBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff2ba0c390cb7de733fa3194b2bc09ee724dc17e","datavalue":{"value":{"entity-type":"item","numeric-id":4194748,"id":"Q4194748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$F19C703C-40F1-493A-B086-8A6BA5904D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"850596316d5e081b5ec4d1111d20081ad1b500c5","datavalue":{"value":{"entity-type":"item","numeric-id":3947447,"id":"Q3947447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$E5F79A29-F555-42BF-B02B-ADEC7CDE560F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"523181021977faad2437a900d8d2ffc5bad3c959","datavalue":{"value":{"entity-type":"item","numeric-id":4193264,"id":"Q4193264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$DD87457E-B96A-4A71-A6FB-653CAAC659FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e62040678950281a1295e4ef2e270fe03444e5f9","datavalue":{"value":{"entity-type":"item","numeric-id":3893672,"id":"Q3893672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$0380B25C-BA0D-42D1-9B29-5A8E917EF8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb8f1262f88a7d67eb934076fa278aaade908f80","datavalue":{"value":{"entity-type":"item","numeric-id":761347,"id":"Q761347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088908$63E2CF16-CE77-4FAF-A20C-5907AF7B5095","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1452538f60299189065e29e3e0c81652d301ff83","datavalue":{"value":{"entity-type":"item","numeric-id":1809834,"id":"Q1809834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72e35eca98e9b7c2144c0bab5457491150591444","datavalue":{"value":{"amount":"+0.8544847369194031","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":"Q1088908$3046F678-73F3-4632-B794-EC2C469A699E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a919cf12c908bbb32a641b63202c736d10f92620","datavalue":{"value":{"entity-type":"item","numeric-id":884028,"id":"Q884028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab8c74d688383292d3eb289c3f8d2d07a8a05b82","datavalue":{"value":{"amount":"+0.8507554531097412","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":"Q1088908$C474D9DD-13CA-4B6D-928A-18FB9D54271A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fa3836e2435d1f5a426130692db4891f8d08a2a","datavalue":{"value":{"entity-type":"item","numeric-id":581236,"id":"Q581236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83e43c13c10d6694556294ac027e39e2012b3c31","datavalue":{"value":{"amount":"+0.8352900743484497","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":"Q1088908$5089DD91-6BCB-4EC3-B7CA-6914BBD406D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"171b639f3342efed2ef0fdc258d0392b4b5e3d79","datavalue":{"value":{"entity-type":"item","numeric-id":1745880,"id":"Q1745880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"864466af16d3f4f9509529dddb7117d9d7ca73ab","datavalue":{"value":{"amount":"+0.8325270414352417","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":"Q1088908$754963ED-08CB-48CD-8E0A-1B99B8627A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82baddc26297f753407831d2f8d8ca8bffb4816f","datavalue":{"value":{"entity-type":"item","numeric-id":3348707,"id":"Q3348707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e1d7fd331bde5348b7183492d0d83d1f36a82f0","datavalue":{"value":{"amount":"+0.8230718374252319","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":"Q1088908$C9D57E2C-942F-44B8-ADB0-9125D72D6DBF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1088908","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1088908"}}}}}