{"entities":{"Q1646575":{"pageid":1657316,"ns":120,"title":"Item:Q1646575","lastrevid":71078283,"modified":"2026-04-13T19:20:12Z","type":"item","id":"Q1646575","labels":{"en":{"language":"en","value":"Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6894019"}},"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":"Q1646575$4AFD20B5-4CF7-417E-B34F-341850BA86B4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"707edbdfc78ca856fde6ba9288dc11a2424aebd0","datavalue":{"value":{"text":"Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1646575$F73DCF09-90E6-4B1C-BF55-02357D8697ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c37e8adb051496c34d1d43c8bc8aaa4da599d37a","datavalue":{"value":"1410.90127","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1646575$FE26B124-1EE8-4C0F-B56A-52280A24F0BD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"886909d9e6c0b912056a90d31e211fb33957d8c1","datavalue":{"value":{"entity-type":"item","numeric-id":1646574,"id":"Q1646574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$C414D41F-1C1E-4127-B637-74539386A4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1bcecf876896eb3bdc6e6294ef59780aec56484","datavalue":{"value":{"entity-type":"item","numeric-id":262439,"id":"Q262439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$5A17E3F9-67B3-4269-B0FB-BFF91DC5308B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc0bd20b49fc5f8c46a35ef243535d5a3fb2bd74","datavalue":{"value":{"entity-type":"item","numeric-id":210498,"id":"Q210498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$D1545601-2C03-4858-BDDE-ED0E2F71533C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"26f62544e3496a6c42798706c99506c8712f0566","datavalue":{"value":{"entity-type":"item","numeric-id":299792,"id":"Q299792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$265CB7E5-6CA5-468D-B2D3-C7BD3D6E9A55","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":"Q1646575$A610A73C-1E7F-41DE-80C9-4A37F4506F15","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e7eb804138ac6b125feddd580efb694a34508093","datavalue":{"value":{"time":"+2018-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1646575$A7F4994B-031D-4B91-9696-78187B1C641B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"90ff60a0506307975d49f2dc6c9de4545ccca9c7","datavalue":{"value":"https://arxiv.org/abs/1508.02940","type":"string"},"datatype":"url"},"type":"statement","id":"Q1646575$99E0C801-A4B3-4C09-9B8F-BA06BBEEF6F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"647f6820b34c5babf7c1ba0590303153b4154973","datavalue":{"value":"This article considers the problem of reformulating an integer program as an equivalent program with fewer integer variables, which makes its solution more computationally efficient. The authors begin with an introduction to linear programming and the affine TU-decomposition of a matrix, which is the technique used for the reformulation. The authors then study the properties of the TU-decomposition and several examples are presented. This very interesting paper concludes with a section of the use of the proposed method for the efficient reformulation of many knapsack problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1646575$585B0B34-B376-4262-BD63-73186026687C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58309c80337e7309a39fa8b39c69e1b722b3cd2b","datavalue":{"value":{"entity-type":"item","numeric-id":590170,"id":"Q590170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$EC94B223-D3A5-44E1-8ADD-A1E82EB8775A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1646575$5CAAB50B-1F41-4EA6-B375-983ED9B82AA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1646575$8EE5A44A-425B-42E3-A63B-EED94E935612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1646575$A2848DD9-1040-42C6-BA69-AB906F52B795","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"013622298d95a8e1e95e8d6366de39bba8361dab","datavalue":{"value":"6894019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1646575$466C2F6F-2A9E-42FF-86D6-26C42157ED99","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1646575$42B063A2-FD94-4761-9546-508536A978EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1646575$9D6640CE-EDA9-4CD8-867D-F4407CA41699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6764c0118db2d07d14b57e53811246b18d98ac7e","datavalue":{"value":"total unimodularity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1646575$1B069843-F051-43D0-AC63-7DC1BC2E4920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e52d5bd4ff68fcfe5e30d52ccb12bb3cde0b929e","datavalue":{"value":"mixed integer reformulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1646575$C10AA359-72B0-4FE3-9F37-AECAF1DB8E39","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":"Q1646575$7E69C3F9-F20C-44DD-B07A-CAE3887F41BE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a5e9bbbee5396fc007e38e5713126259c80ab292","datavalue":{"value":"W2199025894","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1646575$91DCAB6C-8D35-44C3-AC81-BC87AF2D28FE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"548fda7e9611fbf216c095fd5a6afd8badf1cc43","datavalue":{"value":{"entity-type":"item","numeric-id":1281382,"id":"Q1281382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$A982087E-77C4-40AB-8B80-B59F2AFB3BB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a816284c4c369141b3d780ad46a7c82f3360ad6","datavalue":{"value":{"entity-type":"item","numeric-id":4190428,"id":"Q4190428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$63ED4E88-6AE7-453D-A8F0-09FD254CDB54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c428f45fd59035c0a6d5d4500708657a4e58aa59","datavalue":{"value":{"entity-type":"item","numeric-id":2433704,"id":"Q2433704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$67A2B086-3EB6-47DF-BBCF-CB3E900FB747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ae3270243d6ac0c90ef7d895a73e5270008fba7","datavalue":{"value":{"entity-type":"item","numeric-id":1076034,"id":"Q1076034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$8E4C35EF-74F6-4563-8AE1-BF9F3AA58ACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33edac45558a11a5c3028854b5575fd6b9869306","datavalue":{"value":{"entity-type":"item","numeric-id":5470794,"id":"Q5470794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$B8D059FD-41DE-4313-922F-F21DFAA43C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"940a6c288e3a8163a4796a3830b9a1c04437d28d","datavalue":{"value":{"entity-type":"item","numeric-id":4651462,"id":"Q4651462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$8E0C3BCC-191E-40E1-B314-E5A53D7FE58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7655cd20c1d90113818e673a1f9d27e643b882a6","datavalue":{"value":{"entity-type":"item","numeric-id":769113,"id":"Q769113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$AA742328-74F3-400C-B0CD-8A78E622FCCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"714c04d9091ad5013fe045c40dc7cef77ea60ca1","datavalue":{"value":{"entity-type":"item","numeric-id":5408745,"id":"Q5408745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$9ABC07F3-5B10-441E-BD43-12D4CA2E6971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5df2408c5166f2c5365f8bd9e6f2305fde6f0b9","datavalue":{"value":{"entity-type":"item","numeric-id":1214165,"id":"Q1214165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$ECC94D21-B8A8-4319-B47D-7353D4451EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b04f51ad425b4d13fc4f51a11e18e7c0666c3798","datavalue":{"value":{"entity-type":"item","numeric-id":5265165,"id":"Q5265165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$88025146-C097-4985-A963-74996CEFA28A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dcefb9530ad5adb61ec52cb8cc9cce0d8605882","datavalue":{"value":{"entity-type":"item","numeric-id":4376170,"id":"Q4376170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$67623271-235E-4DD5-952B-AA255F0E4C4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39f0aa0478964729bbe8b29a6f7bc3eedd0382d9","datavalue":{"value":{"entity-type":"item","numeric-id":5915844,"id":"Q5915844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$03734583-75D3-4415-AF08-9C1A7F0F4448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b369429581047e1dabd46e6eafe270ef5ac985","datavalue":{"value":{"entity-type":"item","numeric-id":3037135,"id":"Q3037135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$4C4283E9-2F10-484E-8272-2CA428F40D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c9d6ce7d8d26b25a3fdd6df708b802ee00612c2","datavalue":{"value":{"entity-type":"item","numeric-id":3780007,"id":"Q3780007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$2F89D94C-FE2F-4C93-B612-C87A950B14C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe11388c6389a28bb8fbbb89cb458842e08a7c81","datavalue":{"value":{"entity-type":"item","numeric-id":2450673,"id":"Q2450673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$520FF801-84B5-4E2E-8BB6-8555BAE984AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2cab55aaccaf4488f771439cd99dd5ee5eacf3d","datavalue":{"value":{"entity-type":"item","numeric-id":1107442,"id":"Q1107442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$FEB16661-1A1F-4106-9824-10AB92F0F0BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$39C80054-7460-4101-8936-CB63AE7054EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d035f421ab9bd8eaa29b517b29669cf50cb87e","datavalue":{"value":{"entity-type":"item","numeric-id":1144028,"id":"Q1144028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$18027A9E-578D-40CE-9901-C431BFCCFE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d568141cfa2bbe1bad39b2fc0a0993e60e3b129c","datavalue":{"value":{"entity-type":"item","numeric-id":1103625,"id":"Q1103625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$EAFE6A12-D195-40E5-89C2-FCE2DF28931F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f68df2321aa21a610234383ce2bced004c5d23ea","datavalue":{"value":{"entity-type":"item","numeric-id":1198083,"id":"Q1198083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1646575$0499EF6B-6E8E-49D8-A6E0-913DAA69DCE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"406f19f82d93603903f217ff599881b39fbfd567","datavalue":{"value":"10.1007/S10107-017-1147-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1646575$7EA9BAC5-419F-49DC-9E97-3450121FD8C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cab0b76a49e657c1c7558ef4eba24e0dbc70d87","datavalue":{"value":{"entity-type":"item","numeric-id":3565242,"id":"Q3565242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc55ea897cf27a104e86a17725087e14a1404eda","datavalue":{"value":{"amount":"+0.7393203973770142","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":"Q1646575$2FCF173B-34BB-48E2-94DB-DB3F92FB82AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"feb1851a119e10affaa5d58daf1f94965ae26cb2","datavalue":{"value":{"entity-type":"item","numeric-id":1424279,"id":"Q1424279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfeceea5f3c0281ddd5b17313b0190505ffaa928","datavalue":{"value":{"amount":"+0.7387585043907166","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":"Q1646575$1C3F96CC-4D7F-40CF-AC57-A1C4770B1928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eabaf5e79013ceba8b75f3c0c10a7bb475228664","datavalue":{"value":{"entity-type":"item","numeric-id":5162650,"id":"Q5162650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b138e9250d8cb8ec100569146d90c32cb94a850a","datavalue":{"value":{"amount":"+0.7343522310256958","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":"Q1646575$6D684473-C3CC-497C-BE59-5F8D38CAA049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e60f38d3a6a5cd29667ba8a04da108938fad442","datavalue":{"value":{"entity-type":"item","numeric-id":3635140,"id":"Q3635140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e6b3c53bf08c3535a693f2114b9a158a9049fe1","datavalue":{"value":{"amount":"+0.731537401676178","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":"Q1646575$B5F898BD-9CB8-4CA1-983A-F62ED36E86BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd1858a6b71238bf1c09e205861680d67bc152ab","datavalue":{"value":{"entity-type":"item","numeric-id":2583123,"id":"Q2583123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf235cacdd9be8ff927387ad978affaebe99602a","datavalue":{"value":{"amount":"+0.7294827699661255","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":"Q1646575$9758B777-F30A-4041-8617-9B388A1708EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Mixed_integer_reformulations_of_integer_programs_and_the_affine_TU-dimension_of_a_matrix"}}}}}