{"entities":{"Q1736729":{"pageid":1747470,"ns":120,"title":"Item:Q1736729","lastrevid":56831277,"modified":"2026-03-23T17:35:12Z","type":"item","id":"Q1736729","labels":{"en":{"language":"en","value":"An integer linear programming formulation for the minimum cardinality segmentation problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042297"}},"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":"Q1736729$B13619E3-F4AC-4BAB-AAE7-AFB5B40D3FC7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73017c4f8676cdce0947d3448189a62d6a657a4b","datavalue":{"value":{"text":"An integer linear programming formulation for the minimum cardinality segmentation problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736729$1316AF61-7233-4C16-93DD-8A6BA08D07CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"641d1946748c7e1e78c745517f770a140315b847","datavalue":{"value":"1461.90073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736729$6B59AF34-AA9B-4984-A2F5-A5C19A8155E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"234c0e71ca787908f8f3de85909e8cf53e9c9109","datavalue":{"value":{"entity-type":"item","numeric-id":319450,"id":"Q319450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$8887088A-B07B-4913-8074-35A5EC6531D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe1818fc3bc607033158b45b1bc7724d6c22ae86","datavalue":{"value":{"entity-type":"item","numeric-id":411239,"id":"Q411239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$C9369426-AD49-47BD-B2B4-659E0B08D270","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$8F57B246-2A2D-4732-B2C6-8D2ACD57CD4F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-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":"Q1736729$D039A392-10A8-4B2D-A25D-7CAE3B832423","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1d04900978a2d1587beca5c064e1e4110bcc10c8","datavalue":{"value":"Summary: In this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an \\(\\mathcal{NP}\\)-hard combinatorial optimization problem arising in intensity-modulated radiation therapy. The problem consists in decomposing a given nonnegative integer matrix into a nonnegative integer linear combination of a minimum cardinality set of binary matrices satisfying the consecutive ones property. We show how to transform the MCSP into a combinatorial optimization problem on a weighted directed network and we exploit this result to develop an integer linear programming formulation to exactly solve it. Computational experiments show that the lower bounds obtained by the linear relaxation of the considered formulation improve upon those currently described in the literature and suggest, at the same time, new directions for the development of future exact solution approaches to the problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736729$764B8119-E29D-48DB-BF13-D8A05D410637","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736729$97053825-D0D6-4B91-A75E-844BDD716515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736729$3646D87F-CCBC-4736-AE53-F7EC9B6A862B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e27beffea4779e8a96e7c5961e8cc7879483d808","datavalue":{"value":"92C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736729$5D874092-EF94-4912-AC86-FE4DCC5E53C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0591c9d5b6b2354e4a118289a1bba788004d49a8","datavalue":{"value":"7042297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736729$CEAE942E-95FD-4EB4-AE8D-09A4636E6096","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f9de5daa60229cab19240e84428712af1a198c7","datavalue":{"value":"matrix decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736729$7EE4F49A-05B9-4653-9A5F-97D8A086F734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94c3588dff5068f04e6c368f14577f6462bcc390","datavalue":{"value":"minimum cardinality segmentation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736729$2C9EB790-66AC-4E46-B73F-017377EE744F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5f830821080cd8a68b981fd16333959524890e4","datavalue":{"value":"mixed integer linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736729$AAAC1914-91E7-43EC-B831-2D1AF23C0F5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f19c19fba6bbd024a1b736afc45725e70b5f4f51","datavalue":{"value":"intensity-modulated radiation therapy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736729$C67BF596-F897-454A-8A92-42A6C9562EAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f84da733a6bf16e8ab1471ad673f55c94eafd5ca","datavalue":{"value":"multileaf collimator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736729$6BAC378C-AC2B-418C-BF37-7E7D43B57E84","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c43387cc0a057dd99afd8a8c96b593b33d3ed2b3","datavalue":{"value":{"entity-type":"item","numeric-id":17507,"id":"Q17507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$EAAFCF85-9E63-43D1-AD7D-4D9DF71F6D6B","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":"Q1736729$946ADFC0-2DA2-4452-B198-78D65F4A9BD0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"66036d72441b21f72af9ea3974d17f0c96d565cc","datavalue":{"value":"https://doi.org/10.3390/a8040999","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736729$B868E2CE-CB08-4CAB-8088-631B08761EEA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ff45cc3c317f448b707de5c56ffa93a4a01e481a","datavalue":{"value":"W2121510931","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736729$111E59D7-7C0D-42DB-AEA0-F28091393838","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"00f002daf1ce6d912479a199870c05e365ad5b65","datavalue":{"value":{"entity-type":"item","numeric-id":2576339,"id":"Q2576339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$EB9516E7-D6D7-45C6-8BCC-0C12F893D6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdbb2ea1c80deee409021d4b46e2e8f29c5a3323","datavalue":{"value":{"entity-type":"item","numeric-id":1932452,"id":"Q1932452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$1A703BEA-3093-46AE-99DA-67C14D1E772D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e93ac3fa88d1f71f45258e231be427be1c82ef1b","datavalue":{"value":{"entity-type":"item","numeric-id":5902146,"id":"Q5902146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$867465B4-B95F-405A-A210-B32C8B21397B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c78206dddb5105f515efc85fc86101b105cbb20","datavalue":{"value":{"entity-type":"item","numeric-id":845914,"id":"Q845914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$6AA8AE67-E04B-4750-9753-573900154CC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0519d391f4391267ee512e288c2a08d8edfe05d1","datavalue":{"value":{"entity-type":"item","numeric-id":2899023,"id":"Q2899023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$1C094023-54A4-449A-8CF7-DC4F446F9329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c012607b89c8602ca971fe72116b920325513a1","datavalue":{"value":{"entity-type":"item","numeric-id":3612403,"id":"Q3612403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$748E4CE6-AC98-4EAF-B98E-5D9F781111A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14d92794fdb134b1b894470a1e93c3c14bb622a2","datavalue":{"value":{"entity-type":"item","numeric-id":2576340,"id":"Q2576340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$18F70B3F-881B-4CF8-9B33-20A24F42C689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"523f313633d1a26c8bbf21788d8359be6980f824","datavalue":{"value":{"entity-type":"item","numeric-id":765342,"id":"Q765342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$639ABF4B-AFE5-4FE4-8E33-CBBDA674912A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f20edb7d02f55c36123766d9551080ccb8961f9d","datavalue":{"value":{"entity-type":"item","numeric-id":538316,"id":"Q538316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$AA3D830C-0BEE-47A2-9F0D-578EEE2AE0E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a427799f248ab4661491770c6393cce49a6d5815","datavalue":{"value":{"entity-type":"item","numeric-id":2643815,"id":"Q2643815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$5912C31B-D525-434B-827D-F45DC45BFEB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f5e12f4ac734c3a6ec28b39c04992fc5b115720","datavalue":{"value":{"entity-type":"item","numeric-id":955615,"id":"Q955615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$28B2B91A-37A8-4184-A670-2258A6A25A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0c49b2d8bc835d978d0c726442603b83f19d3c8","datavalue":{"value":{"entity-type":"item","numeric-id":3057140,"id":"Q3057140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$6586B495-3FA6-442C-B24F-BC87A3316C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af610cb9712f792a50bfe7cf87e5c3fca789b88","datavalue":{"value":{"entity-type":"item","numeric-id":4146776,"id":"Q4146776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$6E09BDB3-F797-4F5E-A3C0-B766FF6266D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$D35481AF-5D54-4A21-BC86-D277BFC97C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72e783fddd9913b8fee59f04b8a393ada3a3ecf1","datavalue":{"value":{"entity-type":"item","numeric-id":4265265,"id":"Q4265265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$D3813BDF-E7D1-4D1C-B2DC-B9DFF8E5B0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45c8503d841bec6a4163035fecdc0dd4268fa02c","datavalue":{"value":{"entity-type":"item","numeric-id":4537623,"id":"Q4537623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$CA15C0D4-A912-45B6-86D3-572E1B053F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66ca3eed1faadff2e5a921716b97f513e7a21660","datavalue":{"value":{"entity-type":"item","numeric-id":4228541,"id":"Q4228541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$A2FD2300-F686-4D0A-8973-5D43B4741A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac84f9fe9792b594e579370e17f21635e91e355f","datavalue":{"value":{"entity-type":"item","numeric-id":4876077,"id":"Q4876077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$367292A2-1112-49A3-94AB-620AA2D522EB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7784b85f7716d76953b727730e43378d22796b7f","datavalue":{"value":"10.3390/A8040999","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736729$7682D25D-AA8F-4FF6-B372-4BB63C35D210","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08f7fa0d53db88deedf8421d497d61961eee03a6","datavalue":{"value":{"entity-type":"item","numeric-id":2899023,"id":"Q2899023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cbdc94040c543931330609b9bbe28a8b81e9d6f","datavalue":{"value":{"amount":"+0.8188667297363281","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":"Q1736729$CAD87380-E64A-4DD8-8BC1-7AE3D0AE843B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a22d4942b28fa370939fb2f5b8c49faf6922cd1","datavalue":{"value":{"entity-type":"item","numeric-id":3612403,"id":"Q3612403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47209bd07ecd8acc552a24c5fafe17faebd88e41","datavalue":{"value":{"amount":"+0.790229320526123","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":"Q1736729$28703D31-912E-4024-B05E-71CF32B65BD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0ecd9b4be01ede6ebabe71b1c9665ee9004c5ce","datavalue":{"value":{"entity-type":"item","numeric-id":538316,"id":"Q538316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9eceb51aec6cecbfd8c3eda0b9df6e32bd5b1435","datavalue":{"value":{"amount":"+0.7600696682929993","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":"Q1736729$1B658676-1A91-4D81-9E9B-8BD3F114FFEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34002e9d63627be246a03d0524cf16ea3c4a441c","datavalue":{"value":{"entity-type":"item","numeric-id":1801051,"id":"Q1801051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5df0820eb53d62cd02968cd44d58025c81783da4","datavalue":{"value":{"amount":"+0.7569059133529663","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":"Q1736729$3581B8F4-B4FA-4F89-AB9E-6C30A68E2E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51bd9b320b195e14aa1f8cbbf5d914ab78713fc4","datavalue":{"value":{"entity-type":"item","numeric-id":4924115,"id":"Q4924115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf1635e2311ab0ecf0a43b663ae549d60be10904","datavalue":{"value":{"amount":"+0.7513774633407593","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":"Q1736729$DC5D8ABD-FFA5-4A0A-9C35-CF7A2589DD00","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736729$48898B5E-9ADD-45A5-B0D7-7DD185F9C4D4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736729","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736729"}}}}}