{"entities":{"Q2429475":{"pageid":2440218,"ns":120,"title":"Item:Q2429475","lastrevid":51455435,"modified":"2026-01-18T08:00:03Z","type":"item","id":"Q2429475","labels":{"en":{"language":"en","value":"A polyhedral approach to the \\textit{alldifferent} system"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6028714"}},"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":"Q2429475$51908BB1-9FCC-48E5-A7DD-02EF1833BA21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3b48e32630769cd30a395746d0a25422159fea56","datavalue":{"value":{"text":"A polyhedral approach to the \\textit{alldifferent} system","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2429475$EF56BECD-92B3-4139-938A-7894C9B5F5E8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f4203ef40602384285d92e2f57359034238fccd9","datavalue":{"value":"1257.90055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$A807EFA3-E478-4515-BA5D-B7230C0F14AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$E4C8440D-08C3-43E6-ADC9-057BB4059E6C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$C5917913-88F6-4233-8B9C-EBCB7247A861","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"268ac2dcba147836830e83eb305ab981e14718f4","datavalue":{"value":{"time":"+2012-04-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2429475$1595FC90-3124-4E07-A60C-40C3BE5C623C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f1252d1fdba18287c4c7409a675c3b289d2e3f3","datavalue":{"value":"This paper deals with the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The key concept of the analysis is based on a property, called inclusion property, pertinent to such a system. The authors present two families of inequalities and establish that they are facet-defining and completely describe the convex hull of an alldifferent system bearing the inclusion property. It is shown that they can be separated in polynomial time. Consequently, the inclusion property characterises a group of alldifferent systems for which the linear optimization problem (i.e. the problem of optimizing a linear function over that system) can be solved in polynomial time. Under a technical condition, the reverse direction of this statement (i.e., if the convex hull is described by these families of inequalities then the inclusion property holds) is established for systems consisting of three predicates. For the systems for which the inclusion property does not hold, the authors have established another family of facet-defining inequalities and described a separation algorithm of polynomial complexity. All the separation algorithms are incorporated within a cutting-plane scheme. Experimentation, on a set of randomly generated alldifferent systems, has produced encouraging results as the integrality gap in most cases was considerably reduced.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429475$8D7642A8-14D6-4FCC-BF03-C6B2D6354F11","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7ca10dace07064dd4effb574d87223c2ba2af4bb","datavalue":{"value":{"entity-type":"item","numeric-id":587060,"id":"Q587060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$4BAD0780-4E19-4C9D-89D8-578157E8EF52","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$C7EEAB26-006D-4A6E-842C-A41D97E35222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$3F73BBF6-0E20-4B0B-8783-B6E57B05BEA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$E49FC691-650B-431A-BF0E-C6B594C861DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$26790D85-E3D6-4B2D-940B-2FA8B3327012","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8437a8306a3ba18fc8489af3440c23e95bd7757b","datavalue":{"value":"6028714","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$7B6B8A6F-9071-4D5C-830E-EF809A1FE46B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"036913131aeccef2824dc24267ce28d8d9c10584","datavalue":{"value":"alldifferent predicate","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429475$3A496ADC-6C8A-495F-A4E4-42BC9B807603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429475$574E9A53-AEA5-44FE-9D46-3BB3E98CB9BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b80c99afc4950f85b79a2fe3707eb2e870b9567f","datavalue":{"value":"separation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429475$47BA664F-D824-4A64-8BFE-436F9EBB7702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429475$21B9D0A7-9652-4280-A756-74A41C696B77","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"6663be921a3fe3b244879abf2c0c98e00d21e962","datavalue":{"value":{"entity-type":"item","numeric-id":13835,"id":"Q13835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$5938B6A4-84D2-4E65-80A8-18910C4F040A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4d0306a541ac4d64d413698a8167f6dce4fa4ce8","datavalue":{"value":{"entity-type":"item","numeric-id":16269,"id":"Q16269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$723AF513-0CD5-47D5-88EF-1575C155DE23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"e7e435cddb579d4a3e8dec3066c3e3ebb4d7a498","datavalue":{"value":{"entity-type":"item","numeric-id":25248,"id":"Q25248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$8A8D430C-0E55-4CD6-A938-B29C5536EEFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"641b33052682772b91a52cb25a99958701635c3c","datavalue":{"value":{"entity-type":"item","numeric-id":17062,"id":"Q17062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$922829BB-B444-4BCB-A602-D5DF75385298","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":"Q2429475$C004D048-62FB-4DFB-A0C2-A05A2F211061","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74816182e89487af7617416023efaba333d22ae4","datavalue":{"value":"https://doi.org/10.1007/s10107-010-0390-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q2429475$4DF7E1B7-620D-4DDB-9CE9-D081AC7C445F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4cda0e6b8b70685612fd2ddeebb95e26f79a3f4a","datavalue":{"value":"W2146753883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$02F67B31-8360-4BA5-BA7B-E7244DE52AA1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a479ffb181fdb5e7c4cb6f8b27f5a9969978cc77","datavalue":{"value":{"entity-type":"item","numeric-id":1041730,"id":"Q1041730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$32BC9E1E-24A6-4F5D-8627-4BF158EE30A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdeaa94d65205e60fe8ec9077d4d1020ded2221","datavalue":{"value":{"entity-type":"item","numeric-id":5713879,"id":"Q5713879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$3A80855E-E48D-43FE-96AA-B23AC4FD9B26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00b8590c0d71f39254e380b3f8136f3888b1c8b0","datavalue":{"value":{"entity-type":"item","numeric-id":5898776,"id":"Q5898776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$CF449A83-7656-404F-8C96-D6ACD64F74D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a72d3a0c9386de87a8e69632c76ab7724711bd1","datavalue":{"value":{"entity-type":"item","numeric-id":1434071,"id":"Q1434071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$5A0AA4B8-EC42-46DB-B225-4F0BD525731D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56da55f8be07f32ddd0f933b095aa3b070c8a58","datavalue":{"value":{"entity-type":"item","numeric-id":1432020,"id":"Q1432020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$23F543C5-F069-429C-B91C-7FA7896CA776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d767c3983beae13dfdf31367dfd57d300ede6f09","datavalue":{"value":{"entity-type":"item","numeric-id":5897844,"id":"Q5897844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$F0049927-A4BC-452C-B79E-74E7C1527ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$CA6C2145-5A9A-4B44-955B-3D1DB7095640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6aa8bbda13bc362d278699a1d3dd6036a337fe0","datavalue":{"value":{"entity-type":"item","numeric-id":4523706,"id":"Q4523706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$F404B4AB-9D1E-48DB-8AEF-1D9A191400AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34513c7cdceb516d6ad8dc295119d1e36e4804f3","datavalue":{"value":{"entity-type":"item","numeric-id":1961464,"id":"Q1961464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$F5BC1080-C497-493B-84CA-9DC56DB1468D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02ef1c4b0b5c2a1fcf9258512e5536d41b34dc7a","datavalue":{"value":{"entity-type":"item","numeric-id":1414734,"id":"Q1414734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$FFAC6450-62AE-4837-B369-6ADEAE445382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ba7efe24932c0eb2f1b302b8e0267272d08306c","datavalue":{"value":{"entity-type":"item","numeric-id":1610663,"id":"Q1610663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$A9B18404-11FC-48C0-9697-746FDA8FBFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac1abe50aac5b4b2c4f0a6ac7ca24ad19c5d2eca","datavalue":{"value":{"entity-type":"item","numeric-id":2884544,"id":"Q2884544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$CF7AF219-DBED-4999-8817-34647E5C37E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"802833deb74c8bb6fdd15d7e976e3ca238f3075d","datavalue":{"value":{"entity-type":"item","numeric-id":1843433,"id":"Q1843433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$35E1E240-EEA7-4C21-A13B-81FD4B141CAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"916a0417cb69ac3db3ffc788fe840b7896229848","datavalue":{"value":{"entity-type":"item","numeric-id":4473038,"id":"Q4473038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$FD290851-6B69-461D-B312-6AFE3325ACC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"727b055fa2a7a41a93df99d1db3788c2820ad531","datavalue":{"value":{"entity-type":"item","numeric-id":1871974,"id":"Q1871974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$6CC8A0B6-A65C-4634-B2C0-0319901C5968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40c31f24d5376d18d1027b9f8e9c192492e6351e","datavalue":{"value":{"entity-type":"item","numeric-id":5900319,"id":"Q5900319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$809D4EA5-7052-46D4-B004-302CEC7E638C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2d3207af5ea54259747675636827e00e4c927bd","datavalue":{"value":{"entity-type":"item","numeric-id":3612424,"id":"Q3612424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$5B34FE13-D9A4-472B-8DC6-3E816BB2970C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce7be38a80fb42548e4b426cbafa81bb8722cc02","datavalue":{"value":{"entity-type":"item","numeric-id":2884497,"id":"Q2884497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$F2D2AF08-0CC6-4792-A9E6-AD82AE7EE2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b0f12c9e969d42ded787dcf9b2184b0b36eee3d","datavalue":{"value":{"entity-type":"item","numeric-id":1300274,"id":"Q1300274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429475$2E2C922A-96A8-4E1C-9F0D-A3ACF0D9F143","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5903b40ade725a468d395b385ddfd04d5675d81c","datavalue":{"value":"10.1007/S10107-010-0390-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429475$2E884D9E-7174-4071-A9F3-97A9FD76B73C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3252faf4bcd275e324afa99c41bbac58778d74ae","datavalue":{"value":{"entity-type":"item","numeric-id":3094904,"id":"Q3094904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32927915fbc28513e0cc7e28d22f1bdf9f8c78ff","datavalue":{"value":{"amount":"+0.8913090825080872","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":"Q2429475$720B9EB8-674F-4B9D-8A86-9D135094FB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f9fbca150b38c2d8b1fffca06789b3d8cdb3bf9","datavalue":{"value":{"entity-type":"item","numeric-id":2884497,"id":"Q2884497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1fbef4a97e94dbcdb16c2a06f8a457f27f74eae","datavalue":{"value":{"amount":"+0.8821898698806763","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":"Q2429475$4E9C2317-57E1-4F03-AF3E-D281613DEDFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6932c4aa4910f326ff9b81c23f8ee071234f7fee","datavalue":{"value":{"entity-type":"item","numeric-id":3581873,"id":"Q3581873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7cc31c4aa6b930714198dce641e3304e74d238b","datavalue":{"value":{"amount":"+0.8780986070632935","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":"Q2429475$1CD1729B-8882-4430-BFF3-665A293FBE06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4620093df6b637cd694441bf1fb54979be31c3ac","datavalue":{"value":{"entity-type":"item","numeric-id":1785324,"id":"Q1785324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdb1325e65c53ae30788691743e83d58037f5327","datavalue":{"value":{"amount":"+0.8647324442863464","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":"Q2429475$69EE6E87-3C2A-4BE0-88C5-797A9C5D5899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57ea64dd29f73f36d5b9dbfa8fba1030c65b5f2c","datavalue":{"value":{"entity-type":"item","numeric-id":3015605,"id":"Q3015605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2018d816ba0a3d87463987b2947ae2cbecaaa1ea","datavalue":{"value":{"amount":"+0.8586834669113159","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":"Q2429475$E1A25CDD-1C34-4B0E-8C9B-4AF03FA68621","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2429475","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2429475"}}}}}