{"entities":{"Q1080366":{"pageid":1091118,"ns":120,"title":"Item:Q1080366","lastrevid":69916149,"modified":"2026-04-13T11:11:40Z","type":"item","id":"Q1080366","labels":{"en":{"language":"en","value":"An instance of the cutting stock problem for which the rounding property does not hold"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3965819"}},"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":"Q1080366$9B547FC1-8CA4-4C80-A237-60D2B2C6E330","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"89adb71982c8ad32bee205f8c143f13238747edb","datavalue":{"value":{"text":"An instance of the cutting stock problem for which the rounding property does not hold","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1080366$C7D25031-7037-47C8-816B-5538C6E17CB0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ddbc1b3981d9d201f83e8c5c595b6f2e196cc3ee","datavalue":{"value":"0598.90066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080366$E97B4D09-D43D-4E4F-9842-24375C9E813D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"56d1ef35f67560a0a17d137b4c25b103d12ec53f","datavalue":{"value":"10.1016/0167-6377(86)90009-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080366$C2E44F5D-EE0C-4421-BC4F-2A4BC872A7D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37b057a13db29d2ab21bef967529597cf8d764fd","datavalue":{"value":{"entity-type":"item","numeric-id":210527,"id":"Q210527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080366$D38305B7-CF6F-4DF3-A731-514682690921","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080366$1D7C8FD9-34D0-45CB-89FB-C81C08E5FCEC","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":"Q1080366$BB03983B-D1E8-4B93-9597-82062529FFA7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ce3a41109d7697b0fadc2c9d935a9909a060578c","datavalue":{"value":"We say that an instance of the cutting stock problem has the integer rounding property if its optimal value is the least integer greater than or equal to the optimal value of its linear programming relaxation. In this note we give an instance of the cutting stock problem for which the rounding property does not hold, and show that it is NP-hard to decide whether the rounding holds or not.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080366$C9F13CB3-DFDC-49A3-B9F8-F6323D6AC5ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080366$BD1C4B76-2662-4567-82C9-477BC48A6FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080366$3EADDDF5-A939-4E02-BFC0-30B92CC430D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"38e213338db24b8f359e8c3fca9e6e9ae655d7ca","datavalue":{"value":"90B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080366$CDC9C6FA-39EA-4A55-92EC-27D7C8BFDF99","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24b071d7f689812adee7d18926783194ab711f4d","datavalue":{"value":"3965819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080366$31533DA2-FF71-430C-BE50-184318B49927","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ca834784f2b4c9bfe495249efb02810d3d6060d","datavalue":{"value":"cutting stock","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080366$6D7E358A-431B-4436-9002-34205CA10275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d644fdd7128931cecf9b429cd696039a4a29b75","datavalue":{"value":"integer rounding property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080366$89BA6384-5B87-483C-8D3D-FEA18E8D0545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080366$CCBFCF2E-E187-4FFF-A76D-61D2AD11F970","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":"Q1080366$3DD1810E-5514-43FF-B105-5D5F53BA03B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5ae7cc01fff325ceae4df27fa061860eb93a774","datavalue":{"value":{"entity-type":"item","numeric-id":3668310,"id":"Q3668310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080366$304BD58E-0A0C-4349-A71E-FDF44C3F3D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080366$FE3FC86F-2893-4BCC-A6B5-E107E1EA93F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62aca182cf7487a4b1e055b81bd9aae74224c904","datavalue":{"value":{"entity-type":"item","numeric-id":3710296,"id":"Q3710296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080366$5C6684F1-2454-45E9-834F-0D4F350A89AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"55d5179cd6b31fc33287fc8c04f0c947928d8c8c","datavalue":{"value":"https://doi.org/10.1016/0167-6377(86)90009-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1080366$F2F8531B-79FF-4D29-A6B7-C365A260C0FB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c571723d4011bda8f43abbc3f8ba39d1ef114624","datavalue":{"value":"W2014510366","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080366$3D4140EC-05C2-453E-870F-5232A7049D77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"699d678a826199656e74de230b58f64d5db41ed0","datavalue":{"value":{"entity-type":"item","numeric-id":5090148,"id":"Q5090148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6634f99c5775def1d22c16c6acff9b8837d66180","datavalue":{"value":{"amount":"+0.8849118947982788","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":"Q1080366$7B0B1EC1-95CD-4AD2-B948-6D649F4FA3AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6726e83375b353f0d3766a491c099d9134b0609d","datavalue":{"value":{"entity-type":"item","numeric-id":3710296,"id":"Q3710296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be435bb105002c32735443d9a1b40f1b5b400ccc","datavalue":{"value":{"amount":"+0.8544279336929321","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":"Q1080366$8D6946F9-A7FD-46BA-AE6A-2A7A63D8E276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"997a834aa5c4a6a9118de81d4083d50b684ab8e1","datavalue":{"value":{"entity-type":"item","numeric-id":2487734,"id":"Q2487734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d93e33631dc04159f6b36b868cfeace740b52b37","datavalue":{"value":{"amount":"+0.8456775546073914","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":"Q1080366$7250C34D-C809-44C3-8615-C60A4204E3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9500b047933e2b1d59e7c6cb47c62eefb99d32a6","datavalue":{"value":{"entity-type":"item","numeric-id":1127208,"id":"Q1127208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbf01af0d2fa9e2559cc2c9aa867e5f694ad6ac2","datavalue":{"value":{"amount":"+0.8429062366485596","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":"Q1080366$C612B525-FDDA-4144-89A8-3E6EFD5A1E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9437c6498e947f28d01e3bbccf821f5a6197a59","datavalue":{"value":{"entity-type":"item","numeric-id":1298738,"id":"Q1298738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03aefa244eefbfaa9c305d0a4aecce86b54fd3c7","datavalue":{"value":{"amount":"+0.8343235850334167","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":"Q1080366$86C7A2A9-9F4E-4DF5-822D-DECE856851BC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An instance of the cutting stock problem for which the rounding property does not hold","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_instance_of_the_cutting_stock_problem_for_which_the_rounding_property_does_not_hold"}}}}}