{"entities":{"Q2655892":{"pageid":2666635,"ns":120,"title":"Item:Q2655892","lastrevid":79251368,"modified":"2026-05-06T13:29:41Z","type":"item","id":"Q2655892","labels":{"en":{"language":"en","value":"Solving the market split problem via branch-and-cut"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5663129"}},"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":"Q2655892$732A94AC-226D-4E0A-90C5-035DC964E985","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c1e9284e5e1719c229b42ce0defa733bf756c389","datavalue":{"value":{"text":"Solving the market split problem via branch-and-cut","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2655892$6A354827-69CF-4223-AD6F-E67B6119F653","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6977dd97e977be744429d3789985fbcbdf06f5dd","datavalue":{"value":"1181.90292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2655892$CBA58466-529C-4943-BA2A-E2E5720A26CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"632d67886e9931e8e5c8956d7866bcfd502abcf5","datavalue":{"value":"10.1504/IJMMNO.2009.030091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2655892$8C7132D4-C5C4-470A-B0F8-FA6BC61D93F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb60adddcb2a2a6e23d124921ba4f9eeef2c8335","datavalue":{"value":{"entity-type":"item","numeric-id":285750,"id":"Q285750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2655892$AF5BDFA7-33FE-48D3-8694-DF37DC0E9FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27250f49d9c3d87280064d228a43b748b71314df","datavalue":{"value":{"entity-type":"item","numeric-id":206978,"id":"Q206978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2655892$A26C7038-DB3D-4669-9EEA-DB47C8BB287D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"25a31c3bf449a0a732cf6af429b43d73c808e64e","datavalue":{"value":{"entity-type":"item","numeric-id":206977,"id":"Q206977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2655892$18BA686B-2664-41AC-8181-59E03B253D4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbaaecaef2dfa668ea21477d02b4828ae0a87bbe","datavalue":{"value":{"entity-type":"item","numeric-id":405666,"id":"Q405666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2655892$FA25B893-37A3-49BD-9B1F-B4D863FA2B3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6894cb84497d6cc4cfb41cb6f9b81a7ae3fab514","datavalue":{"value":{"entity-type":"item","numeric-id":90322,"id":"Q90322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2655892$4C375891-958B-4193-B504-B5509C1E1A39","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a7d3510fd758262138d162772dc8fd527e4a852d","datavalue":{"value":{"time":"+2010-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2655892$49FD336C-45E5-443C-9197-179A34192C83","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44b937aebb4faa851cba38f85efacc0734d1fe74","datavalue":{"value":"Summary: In 1999 some researchers put forth some small but extremely difficult 0/1 problems derived from the market split (market sharing) problem originally proposed by a researcher in 1978. These problems, offered as a challenge to the optimisation community, motivated a series of research efforts trying several competing methodologies. As part of their testing, they employed both branch-and-bound and branch-and-cut algorithms and reported that branch-and-bound performed poorly and branch-and-cut did even worse. Based on this result they concluded that `standard approaches to integer programming are not well suited for this class of problems'. Other researchers offered similar assessments. In this note we demonstrate that current state of the art branch-and-cut methods, unavailable earlier, is able to solve these problems to optimality. Then we also solve 40 numerical problems to optimality and also find that it works quite nicely on even larger problem instances.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2655892$D718CE35-F3AE-4A5E-90FC-07592E64F9FB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2655892$FC302A16-7694-4493-92C4-B86DEBCDC230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2655892$628FED14-C4DD-42A5-9116-7B1F85F30884","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1aa8c8a669e227a3a6f7dd34e41d0798f245ad50","datavalue":{"value":"5663129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2655892$65ADC613-3131-4BDB-A88D-1742C1F30F5C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2655892$EE58F447-1563-4BCA-B3D2-18D8745E17B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d47f8d779baf8f0f6c7d49a8e35ba721ca6cb915","datavalue":{"value":"small hard instances","type":"string"},"datatype":"string"},"type":"statement","id":"Q2655892$BE0DFBB4-ECFA-4C7B-9532-77B25F83C63E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2655892$07286F64-F380-4E9F-83CC-1FD76AF15FA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89e0547bc5170c50b4b1aab6a2fb0a2fef9af5ca","datavalue":{"value":"branch-and-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q2655892$44F0A8C4-7EB4-433F-AD69-304E93FB8852","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":"Q2655892$3335377A-FF1B-403F-8276-DD2165EF21E6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78e09c37b3bd590aef49453e33147f336c0579c9","datavalue":{"value":{"entity-type":"item","numeric-id":1761840,"id":"Q1761840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8160559358aed900a393a90c9604f272eb986f94","datavalue":{"value":{"amount":"+0.8925428","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$9F6B0A0F-5606-44D8-9243-3AE21170B780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a163dcc38be4ee0770ae4d5beef6cbfcd531dc44","datavalue":{"value":{"entity-type":"item","numeric-id":702346,"id":"Q702346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f1fc14b612ee30b595909234266ed69b7d2ab25","datavalue":{"value":{"amount":"+0.8604431","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$D2A94639-1924-4921-A70F-45D3D7AC9049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e286eab385937a002fb99e092be7be07a7ef5b52","datavalue":{"value":{"entity-type":"item","numeric-id":1720866,"id":"Q1720866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5805c9357c660bb96b9bc348209458e1391fdc5","datavalue":{"value":{"amount":"+0.85164547","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$88C367F8-76F0-43FC-BD36-F53110A16CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2214809bec26e750dfc840919296a882f33242d1","datavalue":{"value":{"entity-type":"item","numeric-id":4973247,"id":"Q4973247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0abf179361d8d6b01252aed39b13a913f5c14c6","datavalue":{"value":{"amount":"+0.8465622","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$BFA76E15-9AA5-4BDA-AC5A-C55FD03BBE12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1741d0b1df691bcc88cf0d8359774fd7125f51d0","datavalue":{"value":{"entity-type":"item","numeric-id":5699674,"id":"Q5699674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bf31a781d3db7c2e4cbc8e6451cf4dc4cbe934a","datavalue":{"value":{"amount":"+0.8447371","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$17C98B0B-485E-45B6-80F0-FC0082D15031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46bd3028f583b1022483e1f2a3fee6fa796f55d5","datavalue":{"value":{"entity-type":"item","numeric-id":1364894,"id":"Q1364894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e33f608a870937139ebe547cbe3cf7b47aa6cdc6","datavalue":{"value":{"amount":"+0.8303804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$2213ACF7-00BA-499C-B0F2-96979F5AD633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51642ad795a7d55fe2c26bc88563fafdf759169e","datavalue":{"value":{"entity-type":"item","numeric-id":827608,"id":"Q827608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2bf0d3436e2d688a45ed07a0dd8a93cf0351590","datavalue":{"value":{"amount":"+0.82964206","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$E1FA7D80-E794-46D1-AF89-38CE633E3A51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffe930a04db5f2bc12a87d5ede5fce3997a2ab36","datavalue":{"value":{"entity-type":"item","numeric-id":952828,"id":"Q952828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"869928c068fa5bcef149168e08d77261deaa80e2","datavalue":{"value":{"amount":"+0.8253151","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$CF40EC61-242A-4A26-9A94-6B5146CB72B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e639054b79294f791bba969362ac833667899be","datavalue":{"value":{"entity-type":"item","numeric-id":3551244,"id":"Q3551244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e4df6f56543c16e7a8ad6562e790b28cb5627ff","datavalue":{"value":{"amount":"+0.8219817","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$428127C7-5705-4773-A00F-D3AA9D74E26C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fd34480fb6b51d52cc88b3cf2b96be803499889","datavalue":{"value":{"entity-type":"item","numeric-id":4644023,"id":"Q4644023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0488c50e738b11a74eef1631b4dc62f8517c36e1","datavalue":{"value":{"amount":"+0.82008034","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2655892$00BF3BC7-F887-4B0A-95B6-59975EB7615C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving the market split problem via branch-and-cut","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_the_market_split_problem_via_branch-and-cut"}}}}}