{"entities":{"Q1961237":{"pageid":1971979,"ns":120,"title":"Item:Q1961237","lastrevid":47431942,"modified":"2026-01-01T17:58:22Z","type":"item","id":"Q1961237","labels":{"en":{"language":"en","value":"Pattern minimisation in cutting stock problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1389502"}},"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":"Q1961237$95DAE1EF-CE48-4D18-99C8-A0272957A21D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a07ef962cacf3d777ed5ccb1a1cd8c75061dcb9d","datavalue":{"value":{"text":"Pattern minimisation in cutting stock problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1961237$85D3046A-1117-4760-AB8C-0EA8CEF64D1B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"689816836a0fb80d1e72d3abd3282aa79b68a657","datavalue":{"value":"0987.90085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961237$3C06CA11-88D9-478D-B42F-F7500CDB01FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"92b93e1a6deb6cdfab3a82dbedf88eb02a7caf3b","datavalue":{"value":"10.1016/S0166-218X(99)00112-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961237$7B03B6FF-F784-4B46-9ACC-9EA4C9806918","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":"Q1961237$63E2B1A4-516D-4E10-9433-7E3022D0A8DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"95ec5b043115e52ee0328702da430700e7365687","datavalue":{"value":{"time":"+2000-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1961237$D85CE6E0-5471-4B59-9FF5-4C36A5368853","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"53b1dfd2f1b737861008a3b7c5f5cba769984d82","datavalue":{"value":"In the cutting stock pattern minimisation problem, we wish to satisfy demand for various customer reels by cutting as few as possible jumbo reels, and further to minimise the number of distinct cutting patterns used. We focus on the special case in which any two customer reels fit into a jumbo, but no three do: this case is of interest partly because it is the simplest case that is not trivial, and partly because it may arise in practice when one attempts to improve a solution iteratively.   We find that the pattern minimisation problem is strongly NP-hard even in this special case, when the basic problem of finding a minimum waste solution is trivial. Our analysis focusses on `balanced' subsets, and suggests an approach for heuristic methods involving searching for balanced subsets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961237$27375AAB-F675-46D0-82C2-DE888374FCC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961237$5C2FAA75-4EA7-45D8-8D32-47F80453760A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961237$47EBA49C-9E0A-4013-B202-9D73CF179D58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961237$C22AF067-F1A3-4042-8B33-583AC643623B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8574d1b4767145c9dba48de57e6b0650a3eba0bb","datavalue":{"value":"1389502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961237$09A77491-CB8E-43EA-9EC0-8870A1847D5B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ca834784f2b4c9bfe495249efb02810d3d6060d","datavalue":{"value":"cutting stock","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961237$B80B75F2-D90C-4D3A-A6B0-76CD7939941D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be3b395a257c345c0b2903d876684ac19a21fb26","datavalue":{"value":"cutting patterns","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961237$5EA3E6FC-34A1-46A4-A90E-0A28A2A0A106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e41fb471c5632503b8716f23269ac7a1a49e160e","datavalue":{"value":"partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961237$583268C3-5541-4F5B-9ADF-539B7954598C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961237$66A8142D-6241-4656-8ECC-81226E9CFFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961237$76B3C956-CF8B-4639-BA46-22F904F840D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03f08a3cbc69e48052a97dab7b19fd1cbcee9fe9","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$4574D3FB-E286-40CF-89FC-C4F6C283C0BA","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":"Q1961237$DB7B0D78-955F-481C-AE42-A39BD913C962","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09a3c4a236e1a86a9306468a70629484f76019f1","datavalue":{"value":{"entity-type":"item","numeric-id":4014640,"id":"Q4014640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$D1AB3E1D-B59C-4E3D-8BF0-991E76AEE191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80be8d9b00447a3aa7fa3d519513073da77863be","datavalue":{"value":{"entity-type":"item","numeric-id":4002885,"id":"Q4002885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$A0808E8E-E2FA-42B3-B1FD-D18A4FF85FE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a215457c438695bb7fc4ab73c68b207d61ff499","datavalue":{"value":{"entity-type":"item","numeric-id":3275357,"id":"Q3275357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$D5B08659-D384-4EAA-9C29-D4F7823083CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02e5846a8a2b23e50649c744d199c26a3ee1cc7","datavalue":{"value":{"entity-type":"item","numeric-id":5328572,"id":"Q5328572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$4BE1E897-0E6C-46D1-B94A-AA7FA9487044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78ff56c33c0cca49bb294fb61a2eb1ca5446e65","datavalue":{"value":{"entity-type":"item","numeric-id":1825768,"id":"Q1825768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$85CB57C7-209A-4CB2-AF4E-B7AECBDF3C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea967d3da9256d0a63f2da47bb550aa1eb20155b","datavalue":{"value":{"entity-type":"item","numeric-id":5905224,"id":"Q5905224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$974EEE9A-1A09-4368-8DF0-5484EA7DD29F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c217a2d6d18296420600ca5fd5cf357d905b79ff","datavalue":{"value":{"entity-type":"item","numeric-id":4726042,"id":"Q4726042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$9C3D39A0-5916-4C8C-B948-BA4C20C060E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee2e68f03d21ee32b901a24182519832deed9cae","datavalue":{"value":{"entity-type":"item","numeric-id":4018161,"id":"Q4018161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$FF05B546-1490-407C-9576-CF1A82DD0C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4d6ae3deccb6bd9dc90817d68dd809a9b2cc293","datavalue":{"value":{"entity-type":"item","numeric-id":1902901,"id":"Q1902901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$3F0E9AA1-B20F-4B10-8FBC-E2D4F0FDF34D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5969d1ecf3c0ad42f52b79d7c081d74fa5dd3dc8","datavalue":{"value":{"entity-type":"item","numeric-id":4880878,"id":"Q4880878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961237$93CE1361-A6C3-41EE-B349-2DB86FDC61BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d076328094041ad834710e73a3f8a8461f52c9ed","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00112-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1961237$774BC9CB-7927-4206-9342-89BAE9DEFDBB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fdbe74a8c83889261c7527d0f39b6aeeb9ec5a42","datavalue":{"value":"W2093285251","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961237$F8DFFDA4-E7C3-4C2B-9F1A-2145033B0E23","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f508d829b0afae44988a102b0636287abfc198da","datavalue":{"value":{"entity-type":"item","numeric-id":429692,"id":"Q429692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e800c6677e0ee8747df42d35971771e8a93a114","datavalue":{"value":{"amount":"+0.8566693067550659","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":"Q1961237$20690579-23D1-4A5C-8CA9-DACA43ECB679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"108071ef4912b6c298c9dede083238bafdba94c8","datavalue":{"value":{"entity-type":"item","numeric-id":4530667,"id":"Q4530667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"565920c32e864cef80c438af2609cf4c8cb10b69","datavalue":{"value":{"amount":"+0.8457517027854919","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":"Q1961237$5EDA9019-0151-4328-BB51-CBA9B81B4117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab05c52900530a67d4b1ed85823c55b8967a576d","datavalue":{"value":{"entity-type":"item","numeric-id":4497274,"id":"Q4497274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd19e9a9bab10e6647e62cebbfa324f68271dd85","datavalue":{"value":{"amount":"+0.8346804976463318","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":"Q1961237$23AAFADE-6D14-43B9-9459-A920DCA6BFED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c04a652d04ec82052c14e233950af87a9ece126a","datavalue":{"value":{"entity-type":"item","numeric-id":4367016,"id":"Q4367016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e891ba6b3e93af7e9d19bb57f41687cca9d2a5bb","datavalue":{"value":{"amount":"+0.8181330561637878","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":"Q1961237$0C2C527B-92D1-4606-B980-D661D7F4DA47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09e78a205399ba5719e988e5a887663d254f4a1e","datavalue":{"value":{"entity-type":"item","numeric-id":2489315,"id":"Q2489315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"057992d484945d31749ea587a51146b7d3af3b19","datavalue":{"value":{"amount":"+0.8138033151626587","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":"Q1961237$9768CB4A-010B-413D-922C-45CB9840B612","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1961237","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1961237"}}}}}