{"entities":{"Q2627348":{"pageid":2638091,"ns":120,"title":"Item:Q2627348","lastrevid":52818911,"modified":"2026-01-23T14:00:06Z","type":"item","id":"Q2627348","labels":{"en":{"language":"en","value":"A mixed-integer model for two-dimensional polyominoes strip packing and tiling problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6724693"}},"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":"Q2627348$BFD2BA0C-728A-4547-BEEF-C0DDEFC33629","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7dad17cec3f1a2c58371feb3a148c1b8886c3b5d","datavalue":{"value":{"text":"A mixed-integer model for two-dimensional polyominoes strip packing and tiling problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2627348$94B33161-A3FA-4FD7-8F28-8522F275D559","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b84bfabaa18af0c9e8e52655197f496b75bf4e6","datavalue":{"value":"1362.90302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$B4AEA300-4265-4E73-B242-5B063E1CD839","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0b17f93aec633be162bdd70032f0cd70dacc860f","datavalue":{"value":"10.1504/IJOR.2012.050147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$90479760-F142-4757-A0CF-00B6F3203CB6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7382e7a1cce62d76e16daa84a33169f59fb7d978","datavalue":{"value":{"entity-type":"item","numeric-id":2627346,"id":"Q2627346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627348$0823E2C5-6EED-4BA6-BEB5-1944E9A4E17D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ff908981af5c0327f7c73be5f711742ae914482","datavalue":{"value":{"entity-type":"item","numeric-id":2627347,"id":"Q2627347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627348$A75DEFE8-E48B-47E2-852F-221E10AE4D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dbf5668b2625c92b0c9d950650749063f9b02a3","datavalue":{"value":{"entity-type":"item","numeric-id":1262081,"id":"Q1262081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627348$7E0D4636-FD6A-47A3-BA9A-CE8368773C39","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627348$AAEBDBE1-4E20-4C24-8A74-F75D3331833B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d49858a0afe4b614990a77fa152712e1ae2b828","datavalue":{"value":{"time":"+2017-05-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2627348$687A1741-2F5A-45E2-BF8B-442AAF19B31B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6749422fd0e2cf2f51c997bc4ea84a3f1fda46f2","datavalue":{"value":"Summary: Two-dimensional irregular strip packing problem is one of the common cutting and packing problems, where it is required to assign (cut or pack) a set of 2D irregular-shaped items to a rectangular sheet. The sheet width is fixed, while its length is extendable and has to be minimised. In this paper, a new mixed-integer programming (MIP) model is introduced to optimally solve a special case of the problem, where item shapes are polygons with orthogonal edges, named polyominoes. Polyominoes strip packing may be classified as polyominoes tiling; a problem that can also be handled by the proposed model. Reasonable problem sizes (e.g. 45 polyominoes inside a 10 {\\(\\times\\)} 25 sheet) are solvable using an ordinary PC. Larger problem sizes are expected to be solvable when using state-of-the-art computational facilities. The model is also verified via a set of benchmark problems that are collected from the literature and provided optimal solution for all cases.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$A6522CA4-AB42-40DE-B24F-23B34970130F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$00130406-35AC-48A9-B5E7-B73B8BEE8C48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$F943243A-7B96-4254-9180-92E2D13FC5B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d37df3eeaabc93671e85ccca30b22399444c5039","datavalue":{"value":"52C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$54C5C2E9-A3B9-4987-8290-272AF0A41582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$5B957851-6657-483A-932C-B152474B1C02","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c1067210cdfa7262482d21aa49fac2765f5576eb","datavalue":{"value":"6724693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$26219B38-4DF8-446E-B441-42EB2868CC01","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be06fa9ba6a97242e2a814e663d52c764aa26c6f","datavalue":{"value":"strip packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$9BFED0C4-B055-428D-A5A4-EC136D49E1B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0470d7a9698e5ceba3367e54959ca52af6c7553","datavalue":{"value":"tiling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$3C291CDD-CFA6-4040-B63A-79A82904B2A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f386261869d66d4919d19db340e7f02ede67ffea","datavalue":{"value":"polyominoes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$833FF3F7-A03C-414A-96EE-B80395C0E4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73a8ed176b208f4c2d3020ca5b416c3793376529","datavalue":{"value":"2D polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$B0630401-F6F4-4BE6-85DE-46C41F80C1A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08823d8721d2e03d88e4cef8093d074f2f680a23","datavalue":{"value":"mixed-integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$A3FB7EAE-A5C9-4652-9EDE-049FB95DA889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3a99de004f2e4e874de2a470310e7cd24e079ce","datavalue":{"value":"MIP","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$69F5E641-3F1C-49BB-A416-1506583D3B1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9778e1c50ad040fdbd47bced21cb9b0823eb5ce","datavalue":{"value":"modelling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$EC17D8A6-071A-47E9-8CDD-391BB3BA3EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a31d7fc03dcfb87a4848b4e1446a9202f8900f0","datavalue":{"value":"stock cutting","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627348$E195EED3-B2C0-43B9-B288-7426A77F6C1A","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":"Q2627348$507A4752-913E-47D6-A913-CBE0A1D16548","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f948a938fe82e9454d236d0c762752a7b8cc29e1","datavalue":{"value":"https://doi.org/10.1504/ijor.2012.050147","type":"string"},"datatype":"url"},"type":"statement","id":"Q2627348$F4F0E6A0-EFFC-446E-ADB2-C4D4DFBC49D0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eeb004475cad4f8186909c80fddc370c7973f858","datavalue":{"value":"W2162827621","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627348$3F2BFA83-336E-4E8C-86F1-CB6A03134FC2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64b46af36049b481a854ec2c3bbb94beb9c5d755","datavalue":{"value":{"entity-type":"item","numeric-id":323210,"id":"Q323210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f14e365e5d267a0986123d4ce40aee9e0abe4a52","datavalue":{"value":{"amount":"+0.8465231657028198","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":"Q2627348$D0E2BDFB-0348-4124-849E-7BFA2157CCA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"259e13a710f2ea298b12e7e862abcb0c61c4adfe","datavalue":{"value":{"entity-type":"item","numeric-id":256688,"id":"Q256688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b3fd40ca087863f8309fa4dbffb301d3c0330a1","datavalue":{"value":{"amount":"+0.8322237133979797","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":"Q2627348$D82C335F-FE44-4731-9D8B-FEEB9CECB7A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e39d88f6a7ed143dbf3bbf9409a109ee59d14758","datavalue":{"value":{"entity-type":"item","numeric-id":1652422,"id":"Q1652422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7e7b9c023c1b5d44ce35c50041259888e350258","datavalue":{"value":{"amount":"+0.8231338262557983","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":"Q2627348$29A85AEA-6B43-4DD3-9D68-318F12945486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4303ecc96a9e57c108acbe2c5a85569b52c79cf7","datavalue":{"value":{"entity-type":"item","numeric-id":1756757,"id":"Q1756757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfaa3dedfe68a3a946d6d36d6152eb930b8ebb9b","datavalue":{"value":{"amount":"+0.8201680779457092","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":"Q2627348$BBF199F6-1DAE-4519-B621-0032C0422CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37852c93e213b88886bb733823b444215477cece","datavalue":{"value":{"entity-type":"item","numeric-id":3835624,"id":"Q3835624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b9614da1d34e025471e1c3cb16508e1b0e7f116","datavalue":{"value":{"amount":"+0.792449414730072","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":"Q2627348$A609356A-030D-4593-9339-9C0FA247F726","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2627348","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2627348"}}}}}