{"entities":{"Q1117840":{"pageid":1128589,"ns":120,"title":"Item:Q1117840","lastrevid":49259392,"modified":"2026-01-06T20:58:53Z","type":"item","id":"Q1117840","labels":{"en":{"language":"en","value":"Layering strategies for creating exploitable structure in linear and integer programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4093180"}},"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":"Q1117840$E7CFB1AC-E304-4C1C-9B31-F191D4FE4BCF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bdf19ae3274b23fa75486f54d767c7874ed642d9","datavalue":{"value":{"text":"Layering strategies for creating exploitable structure in linear and integer programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1117840$9954847D-F2E8-46DF-A07B-7AC5360B6E6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6c8638965adf3a7a4001cbaec35a7a2c56c1a33d","datavalue":{"value":"0667.90070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117840$088AA04B-0DF0-4251-97CA-0507DCF8E5C3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1fe64af209fad4a9fe9bb0e9220cd002d5ad8ff6","datavalue":{"value":"10.1007/BF01580728","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117840$16E40D92-2ED4-4B65-9580-CB775CBBAA96","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bba0dc06d9e863feee266304b6624ac54f793c4","datavalue":{"value":{"entity-type":"item","numeric-id":168083,"id":"Q168083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$E9CF2FF3-A4D2-4127-B4A6-62B67C07CF98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebc81156bfa770990eb6930939f0807d36373a6b","datavalue":{"value":{"entity-type":"item","numeric-id":1072450,"id":"Q1072450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$49046407-59F1-4C5E-AB17-787B6E0BA30F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$90C57D6F-ED1D-40B9-A564-7F4EE2021638","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1117840$CB17C7F8-616C-48A9-94DB-28866F49E436","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e5d95ffa59667d5b9d68bdbb44595171d0a363f","datavalue":{"value":"The authors describe the strategy of subdividing linear or integer programs with special structures (like network structure) into layers by splitting variables. Starting from (P) min cx\\(+dy\\) subject to \\(Cx+Dy\\leq b\\), \\(x\\in X\\), \\(y\\in Y\\) the rows of C, D and b are partitioned into r mutually distinct classes and the equivalent problem \\((P_ h)\\) min cx\\(+dy^ h\\) subject to \\(C^ kx+D^ ky^ k\\leq b^ k\\) for \\(k=1,...,r\\), \\(x\\in X\\), \\(y^ k\\in Y\\) and \\(y^ k=y^ h\\) for all \\(k=h\\) is obtained. Taking the equations \\(y^ k=y^ h\\) for \\(k\\neq h\\) into the objective function one can get a relaxation R(w) of the form  \\[  \\min cx+\\sum^{r}_{k=1}w^ ky^ k\\quad subject\\quad to\\quad C^ kx+D^ ky\\leq b^ k  \\]  for \\(k=1,...,r\\), \\(x\\in X_ 0(\\supseteq X)\\), \\(y^ k\\in Y_ 0(\\supseteq Y)\\) for \\(k=1,...,r\\) where \\(w=(w^ 1,w^ 2,...,w^ r)\\) fulfills \\(\\sum w^ k=d\\). To strenthen R(w) simple parametrized bounds on the components of each \\(y^ k\\) can be included: \\(L\\leq y^ k\\leq U\\) for all \\(k=1,2,...,r.\\)    The authors discuss a subgradient approach for solving this modified relaxation where gradually L and U are changed forcing all vectors \\(y^ k\\) to become equal. This approach seems also suited for parallel processing. Computational results on a class of personnel planning problems are reported.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117840$7E5D54A4-E937-414F-9080-25C0199AFAE3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117840$50196760-5AC7-4B96-84A1-F44D3CE32039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117840$16525604-4FA8-4012-AA0D-80CAB33BF846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3cc0a69df9833551a36455c96769c276a21473cc","datavalue":{"value":"49J52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117840$77D0CBD1-8427-4F31-A546-68D5539C480D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117840$EA2D636A-DFD2-4896-A5B5-130DD546C771","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91d1070d349494845f4416b8bb44cf01fa438617","datavalue":{"value":"4093180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117840$9CAF3A93-586B-4526-B1ED-78FE4D2B549C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"baf060195c8fd22c198301b6d5d6829607bb5eb4","datavalue":{"value":"layers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117840$613CDE7F-8930-4D0A-93CA-5090DEF91EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51bc0c453e3352577d857a6c5fd53eb35c968586","datavalue":{"value":"splitting variables","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117840$A8931F65-234D-4FF8-90D2-E811AC15949A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80f4dd4f78701ebd2ce97577dc38b61dd60db1d7","datavalue":{"value":"subgradient","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117840$8980D3F6-551D-4109-8D73-98D075E8CFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b431e398f975b5a77647ec43799a42637ea93cf0","datavalue":{"value":"modified relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117840$FF864293-3D58-4C70-8EE7-2829958C1F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db5e0888fa9957c443e210eb3c88f717e276ae13","datavalue":{"value":"parallel processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117840$C1B476D8-6862-4F72-92C7-65AE8CAF53A6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a45374906fa7445234d8f571198ca1750e8882a","datavalue":{"value":{"entity-type":"item","numeric-id":170644,"id":"Q170644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$D3994BFE-2E54-4004-B526-DCA66EA32071","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":"Q1117840$FB5B95EE-E73D-4AA5-990A-36E3B44E83CD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"79d94454d6dd28eaed2641469bf5dda07fb58a09","datavalue":{"value":{"entity-type":"item","numeric-id":1108179,"id":"Q1108179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$F7C4CDBF-5310-43D1-8EC5-5E7D051BEBC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6f3ca403e15e27136224a54338c02fc88f4b1de","datavalue":{"value":{"entity-type":"item","numeric-id":3330988,"id":"Q3330988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$4B33A0D4-ED9E-4F72-97B6-DB3FFBFF4385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea022308c2e9ea53b119c830963fd8056d7c2adb","datavalue":{"value":{"entity-type":"item","numeric-id":3885552,"id":"Q3885552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$611BCD82-4CC7-4958-A2C7-3E871ECA63F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5689fa65385b2c188bfb367432ebbda01751a974","datavalue":{"value":{"entity-type":"item","numeric-id":3800056,"id":"Q3800056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$3916D571-AF52-41A0-ACAA-6C029E8ED851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87de5db3c8e4dbdc3c629dbd6d7be056670a6ebb","datavalue":{"value":{"entity-type":"item","numeric-id":3693261,"id":"Q3693261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$0BBBC212-D9BE-413B-B99E-0FD864D9028C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"454c9d51eabbf4c604940d776c4fe47b63969e09","datavalue":{"value":{"entity-type":"item","numeric-id":3712095,"id":"Q3712095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$C276839E-2C4D-4713-BB50-B65972372DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12e6198b78831ce91556d24190a3c986ef0555c","datavalue":{"value":{"entity-type":"item","numeric-id":1142044,"id":"Q1142044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$5E2B2D56-70DE-4713-9986-F6DBA1856CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"904a534fa0cc92ed1d19a14502e65bdf0f62127e","datavalue":{"value":{"entity-type":"item","numeric-id":5550289,"id":"Q5550289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$97BE34DD-688F-4245-A9FC-63F67B733361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4823f04d9fb1b5978ca3b1fa99933ee2850940a9","datavalue":{"value":{"entity-type":"item","numeric-id":3049827,"id":"Q3049827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$2D560820-7095-4613-B80A-C9E76A3E4326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7961834e428c1229065c0bccdd8e35f160408252","datavalue":{"value":{"entity-type":"item","numeric-id":3887226,"id":"Q3887226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$5D9DAAB1-CB89-402C-8419-A4ED9EF04938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d9d68d587114452b9502e8878a09533a09348e2","datavalue":{"value":{"entity-type":"item","numeric-id":3780005,"id":"Q3780005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$69FA1A9A-DCEE-4D31-AC64-F2107FD6A73B","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":"Q1117840$C6B19559-E2D3-4191-A8BB-558763F4304B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91deb465da2e31dcfcb64a601e82233cb3168c53","datavalue":{"value":{"entity-type":"item","numeric-id":3968759,"id":"Q3968759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$39D71310-D917-4B9F-86AA-3FBA1218FF13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88185dcc702c1bc606c4605598075be4f4e07995","datavalue":{"value":{"entity-type":"item","numeric-id":3342177,"id":"Q3342177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$7D5C61BB-7166-4020-8ECD-DBFA78725664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"350d2dc4ea7f74a16a015b87a89930d226a597af","datavalue":{"value":{"entity-type":"item","numeric-id":3895231,"id":"Q3895231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$348F376D-E9B9-4BB3-B6F8-862DC4C6A517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02270d2afac6cc5a3bf3585e3f0d920175d3d313","datavalue":{"value":{"entity-type":"item","numeric-id":3893617,"id":"Q3893617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$B520471E-4111-4514-AC0C-38B2EB18AB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d1b4fc1cd8fb80881eeb4aa5cf6e17bff174252","datavalue":{"value":{"entity-type":"item","numeric-id":5588251,"id":"Q5588251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117840$3740B336-A4FA-45E1-A599-DB3321EFF4D2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8acafe9ba9c41ec1192b1c46e6e86510d3e76af9","datavalue":{"value":{"entity-type":"item","numeric-id":1110459,"id":"Q1110459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7bc6d29b15aa475705643a1c1fbf122d2a6ea47","datavalue":{"value":{"amount":"+0.7751960754394531","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":"Q1117840$9F4A29F2-7EDB-48DA-9ADB-9CE2AA670521","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":"f24d1b81639278c68fbf2048d2dc6cc0c48b65fa","datavalue":{"value":{"amount":"+0.7712790369987488","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":"Q1117840$FE5B6105-38C8-4621-829B-A9A5C6FD97F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc0bcd7eb3d6276128e3af21b77917908eedf42a","datavalue":{"value":{"entity-type":"item","numeric-id":4254875,"id":"Q4254875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f720c64b55568c7bc8dd8f3d23fd2874d0ea7d23","datavalue":{"value":{"amount":"+0.7645975351333618","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":"Q1117840$0D5B5268-8E23-4EAD-8412-669B9AE37E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11a5105cd60e9fbd64a5f4e27613569debde17d1","datavalue":{"value":{"entity-type":"item","numeric-id":1348247,"id":"Q1348247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6fcf44b24d8e39498ec5cf5a942b146fc687f1a","datavalue":{"value":{"amount":"+0.7625201344490051","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":"Q1117840$B4624B11-C59A-4374-BB8A-A2165E4ADEC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2f786fc509a327e326423855b229f9e882500d2","datavalue":{"value":{"entity-type":"item","numeric-id":1206388,"id":"Q1206388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5ad7209c7647984a20e3610115182802d7d0bd7","datavalue":{"value":{"amount":"+0.7587612271308899","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":"Q1117840$BD0C0451-55C7-4550-91EE-A06BDFDB9D92","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1117840","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1117840"}}}}}