{"entities":{"Q1109677":{"pageid":1120426,"ns":120,"title":"Item:Q1109677","lastrevid":66451026,"modified":"2026-04-12T10:09:54Z","type":"item","id":"Q1109677","labels":{"en":{"language":"en","value":"A unified approach for price directive decomposition procedures in integer programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070629"}},"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":"Q1109677$67AB8273-BAF2-4495-B735-C721ACF411FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"36fa10919d0fb812f20cc3df239ad2728d82d6d5","datavalue":{"value":{"text":"A unified approach for price directive decomposition procedures in integer programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109677$0E64C68B-5B30-4E47-BCD3-2E1102FFE452","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a538f3b218de210d174d25c6c601071646da2699","datavalue":{"value":"0655.90051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109677$0BBB4C6A-7E85-46BB-A712-4527461F142D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6975081fad008dda3895f64b22cac2494d48bad5","datavalue":{"value":"10.1016/0166-218X(88)90077-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109677$99E96A2B-EDBC-46D8-A03D-37B00D695B67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"793d9801045cf875d7f45164ae24d709a53bcfe9","datavalue":{"value":{"entity-type":"item","numeric-id":1097164,"id":"Q1097164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$C2F5A8A2-5DEA-411D-AF5B-3BAD66F185D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8050f28ece59af97462919553341c2e297330189","datavalue":{"value":{"entity-type":"item","numeric-id":878219,"id":"Q878219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$6DBFDA47-5EC8-4061-8014-BFCCD065F2B3","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":"Q1109677$D7A5A99E-12C6-4652-88BA-2D9B82E59D89","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":"Q1109677$20C37DD4-A64C-4047-8742-82AF339C894A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"83e2237a2fae08226b1f3f7ee3b8ca1e37b48bee","datavalue":{"value":"The subject of this paper is a generalization of the Dantzig-Wolfe decomposition principle to integer programming. The following decomposed optimization problem is considered:  \\[  \\max \\quad cx,\\quad s.t.\\quad A_ 1x\\leq b_ 1,\\quad A_ 2x\\leq b_ 2,\\quad x\\in Z\\quad n_+  \\]  where \\(c\\in {\\mathbb{Z}}^ n,\\) \\(A_ 1\\in {\\mathbb{Z}}^{m_ 1\\times n}\\), \\(A_ 2\\in {\\mathbb{Z}}^{m_ 2\\times n}\\), \\(b_ 1\\in {\\mathbb{Z}}^{m_ 1}\\) and \\(b_ 2\\in {\\mathbb{Z}}^{m_ 2}\\). Typically, \\(A_ 2\\) has a blockangular structure consisting of several blocks, where each block corresponds to a subunit and thus defines the local constraints for each subunit. The decomposition procedure may be built on one of the two basic solution methods in integer programming: branch and bound (this case is treated in Section 3 of the paper) or cutting plane (treated in Section 5). The necessary background for the application of cutting plane is given in Section 4 which deals with the superadditive duality for mixed integer programming. The following basic result of the paper is derived in Section 6: The subproblems of both solution methods are of the same kind with a convex, polyhedral objective function to be maximized over a polyhedral constraint set. In Section 7 the important case with blockangular constraints is described and in the last section a small numerical example for illustration is solved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109677$8EAE38FE-816D-436D-9A31-E1A648EFA13B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109677$4D18B4D0-8178-4954-847F-2DDDC18341FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109677$A3D6462B-F0AB-469E-8EFA-171C1F82206A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b1e30381eef814dbd2680bd7165473d200e6c7e","datavalue":{"value":"4070629","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109677$DDB6EDD2-1858-486C-8369-5625E6A9F3C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e56b362af64b0d4e893c49124bc5a203a2437926","datavalue":{"value":"Dantzig-Wolfe decomposition principle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109677$E270A68D-7C5C-4BBD-867A-634EA0B853F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7054aa5fc84df8b16412bce01906ea942babf35a","datavalue":{"value":"blockangular structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109677$DC3C32A8-86DE-4BB3-A829-1211F3F17A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109677$D13419C8-DCFA-4AC7-B094-901FB7C3D76C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52a177bb6db11512fb7fada7b7687e9a5462877a","datavalue":{"value":"cutting plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109677$3E1578D9-08D2-4F18-8200-7EEA41D1E2A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8237f5cb570935364c2d30b26f56e9a4f9e4d862","datavalue":{"value":"superadditive duality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109677$E5EADDE1-3014-4F66-B388-6E9D0EACF831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ccb41c455e5a622a3bd5ae1c054bdabd8d1f8b6","datavalue":{"value":"polyhedral constraint set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109677$C21BDFB9-772E-4722-B52A-EBBE5826AC32","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"326ddcc4cf83798840f8add4c5dc03a5586d27e6","datavalue":{"value":{"entity-type":"item","numeric-id":420903,"id":"Q420903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$B463586B-D681-4885-A03B-C36E616D71E5","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":"Q1109677$88E18AE0-042A-409A-994E-85B25809AFE6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b431229bc3c518c0dc20cec0b1256e250a5efed2","datavalue":{"value":{"entity-type":"item","numeric-id":3941194,"id":"Q3941194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$D9EC426B-1CEE-4D48-9FE0-2BB27B98D780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37c5e27eec0774518336b3abae02fae87ec5e720","datavalue":{"value":{"entity-type":"item","numeric-id":3716854,"id":"Q3716854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$65F37F48-0978-4E6B-BEB1-60A234E866BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3b8e688a7ba5ece1709f16703ff3da45cc27bb7","datavalue":{"value":{"entity-type":"item","numeric-id":3288564,"id":"Q3288564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$F9FC8718-9E98-42F4-AFCC-E6D713466846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afb6810cf4b4853a9f5e89238d02c40c44c92c4a","datavalue":{"value":{"entity-type":"item","numeric-id":3666564,"id":"Q3666564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$1EAE233E-22AF-4D01-B7D6-9614B865D6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa74c0bb2c71d8d24f83c953c7f1811531f8473b","datavalue":{"value":{"entity-type":"item","numeric-id":3214706,"id":"Q3214706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$C437A6AF-4518-438D-960F-0CA943AC716A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"154bef8647ef4c0e418f3ad8ed897028f56ea919","datavalue":{"value":{"entity-type":"item","numeric-id":3272914,"id":"Q3272914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$0A4E90FB-29D7-4848-8F44-231CF8AB5C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f6e6c485ffd8db53c78a3185c52a9638a8b8863","datavalue":{"value":{"entity-type":"item","numeric-id":3885525,"id":"Q3885525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$0A454F95-8171-4402-B991-50E6A7038563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcadced99934f5835ba4111e4b0027afb05a3651","datavalue":{"value":{"entity-type":"item","numeric-id":1257827,"id":"Q1257827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$1E768240-1E6D-4A2C-A057-9F0D99C48B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a15baf5ed9b034ca898630c81f59220bfeb9befe","datavalue":{"value":{"entity-type":"item","numeric-id":5183269,"id":"Q5183269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$8CD55DB3-F345-4C78-8E01-7BA84B122B9D","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":"Q1109677$77645413-3305-42A3-AEE8-87A612ABCF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ffabdaa6c36fad603a520760fc3938a8d40649b","datavalue":{"value":{"entity-type":"item","numeric-id":3908768,"id":"Q3908768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109677$C0BCCFEC-FB56-4A49-9023-C4106AB3C8A8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5b92b291d1cebea5cd76043e17b65e7a6f27fbb","datavalue":{"value":"https://doi.org/10.1016/0166-218x(88)90077-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109677$1A4A1FD7-3E36-48E4-8CFE-359A4E63BB36","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bdf28790dc7c005f66930b4357d5ebfa7817b0e2","datavalue":{"value":"W2014220159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109677$AEAB5BBF-A64D-4C1B-BA9D-8C1F0636E65E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"899d25b70cb30dd0564f07183877b1c776a51246","datavalue":{"value":{"entity-type":"item","numeric-id":3372333,"id":"Q3372333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e73ddca2710db8a91b190b69704e5779b1bb04e","datavalue":{"value":{"amount":"+0.8361065983772278","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":"Q1109677$37082140-B084-4A80-B95C-E5038D5624F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4ca72a99c38f1e9cf1361acb1a39aaf552ad818","datavalue":{"value":{"entity-type":"item","numeric-id":4530641,"id":"Q4530641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9e3c706c49bf511efe2d006b65762add60940a4","datavalue":{"value":{"amount":"+0.8336219191551208","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":"Q1109677$B2C70D3F-7F29-42C3-9BA1-A11A1BB03679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25931f531419f4a13d49ed92e96e19d327237de6","datavalue":{"value":{"entity-type":"item","numeric-id":3716854,"id":"Q3716854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cfe0745efc861167b92f61ca7b82114cb3cfba6","datavalue":{"value":{"amount":"+0.8113871216773987","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":"Q1109677$22932480-7851-4BF6-A677-15CD1D023957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5fca1788d2c6017ed13d16c7f9e9a8351e5e2da","datavalue":{"value":{"entity-type":"item","numeric-id":684317,"id":"Q684317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"048a7f0973f8e0cbfa5a76c0f81e52989a861d6f","datavalue":{"value":{"amount":"+0.7893977165222168","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":"Q1109677$73B2B702-1DB8-409A-9778-3BD4BEEF6689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2baaa101d00e51233e971e0ee6f2839017fb66c","datavalue":{"value":{"entity-type":"item","numeric-id":3197617,"id":"Q3197617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eb1dc27baf92cbf7492c41d31919171c3a06154","datavalue":{"value":{"amount":"+0.7889227271080017","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":"Q1109677$D571A5BE-4ECD-45E7-ABC0-6538EF0039B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A unified approach for price directive decomposition procedures in integer programming","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_unified_approach_for_price_directive_decomposition_procedures_in_integer_programming"}}}}}