{"entities":{"Q1612006":{"pageid":1622746,"ns":120,"title":"Item:Q1612006","lastrevid":70974585,"modified":"2026-04-13T18:37:43Z","type":"item","id":"Q1612006","labels":{"en":{"language":"en","value":"Totally tight Chvatal-Gomory cuts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1790728"}},"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":"Q1612006$EF1BD92A-802E-4EDD-A09F-034769310648","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a21d5724b2916aa1d87e8f9cc21f23e24dcc49ca","datavalue":{"value":{"text":"Totally tight Chvatal-Gomory cuts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1612006$78210C02-3920-4FDC-B077-3BAFBAB43BA4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f70c8707284cc91749a0a668168fee2df877a4dc","datavalue":{"value":"1027.90061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612006$7FA58504-A6C6-4016-9D1D-5B12CB658D4C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"160da307597b6bbb96ae966cb3ddd02d1bdd4dbd","datavalue":{"value":"10.1016/S0167-6377(02)00111-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612006$1506C270-DBDC-41E4-9951-F6904D475D1C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7cc27fc1dd4236c294e0ec74bd11801150d0f456","datavalue":{"value":{"entity-type":"item","numeric-id":185370,"id":"Q185370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$D2FF3215-885E-4866-9775-B71575B702E9","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":"Q1612006$9AD21730-919C-4113-ABB0-F6F16E5BBCF2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"142362e6d8f26628ca200c5bf9158be42ab9f824","datavalue":{"value":{"time":"+2002-08-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1612006$158E553B-08B4-48BC-8CB6-6452C75B449F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"736e21e0be3dff897508dc1eada6543bc63c8ca6","datavalue":{"value":"Let \\(P_1\\) be the integral hull of \\(P:=\\{x\\in R^n:Ax\\leq b\\}\\). A Chv\u00e1tal-Gomory cut is a valid inequality for \\(P\\) of the form \\((\\lambda^T A)x\\leq [\\lambda^Tb]\\), where \\(\\lambda\\in R^m_t\\), \\(\\lambda^TA\\in Z^n\\), \\(\\lambda^Tb \\notin Z\\), and \\([\\lambda^Tb]\\) denotes lower integer part \\(\\lambda^Tb\\). The author gives a polynomial-time algorithm which, given some \\(x^*\\in P\\), detects whether a totally tight cut exist, i.e. whether there is a Chv\u00e1tal-Gomory cut such that \\((\\lambda^TA)x^*=\\lambda^Tb\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612006$0C4F43BB-7BE3-4DD9-81F9-9E0DDF62219C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612006$0AEDA3AA-2DCF-4C7E-9F8F-907019FB0CCE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4a271a2cf97368f2f9f247e82b178a7ce6df072f","datavalue":{"value":"1790728","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612006$0F13E20D-DC10-4495-8EFE-0D6B9DD94EAD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612006$67658CAD-5C08-4F0D-B82B-CC36B8A5E8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be3f5c88d3db777a4bdd3348a5d62b7e04a937f6","datavalue":{"value":"cutting planes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612006$EE465905-BDAE-4AE0-A5B8-566DE55FF08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b80c99afc4950f85b79a2fe3707eb2e870b9567f","datavalue":{"value":"separation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612006$F06A5976-2799-48AD-AD5F-70260201B35E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d37f52485aed20b3a80c12d133c34b354959045","datavalue":{"value":"Hermite normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612006$513E68FC-08A5-4FDB-92F0-24F1C71C5887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c00a37c0b1e11734a8b99335a0ec7e0ff7a4d4e","datavalue":{"value":"Chv\u00e1tal-Gomory cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612006$70929D93-FFF5-4AD0-8FBD-579B337F038C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612006$2A0F3963-2DCF-4E47-84CE-164490ADBF46","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9d84644695ef1cd5b7b03362985ba394085d637e","datavalue":{"value":"Q57702369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612006$B8EEB245-868F-493B-BC61-D6AC1A69203D","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":"Q1612006$FCBCE950-F345-40A9-B860-E0C30B53EE45","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"378977ff2fe43fb89f5a77c317ec4d0962da7131","datavalue":{"value":{"entity-type":"item","numeric-id":5704040,"id":"Q5704040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$B4CCC969-8377-4E08-8683-C5E495A8B7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c51f1adfec3e4c1da1bdeb625927be606d3bfaf6","datavalue":{"value":{"entity-type":"item","numeric-id":1814791,"id":"Q1814791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$E661AC41-00B1-4A8B-BA4C-4DC501544402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"102685a85dbcfd492aff0eacd82ee4bb754b87f2","datavalue":{"value":{"entity-type":"item","numeric-id":1970294,"id":"Q1970294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$E71E70A1-41C9-4E55-8B73-867912752CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e07015eece7d16bf1d7f8ae2cc9a5f926bb3bc44","datavalue":{"value":{"entity-type":"item","numeric-id":5101435,"id":"Q5101435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$9C6D2980-0DF0-4C1E-A368-A73033FBC3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa9316bc21130945e76158a0803667b9b47faaef","datavalue":{"value":{"entity-type":"item","numeric-id":2557712,"id":"Q2557712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$199E5C11-0055-4325-9113-20D985D7357A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$D85F9F72-5BD0-4881-ADF4-4F88148EDF0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43798c19208231d39c6c4f059a0476d674a2816f","datavalue":{"value":{"entity-type":"item","numeric-id":4149476,"id":"Q4149476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$A53AB8D2-3CD4-4D18-80DC-BA07164C7799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b9fff83e6553512ded6532e471b53868813421e","datavalue":{"value":{"entity-type":"item","numeric-id":1125619,"id":"Q1125619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$6F73C759-C965-4B74-A81D-E347DDB81B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb37c4b87d6bb6997e3216893bc89a76e7cb05a1","datavalue":{"value":{"entity-type":"item","numeric-id":5341335,"id":"Q5341335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$E009BF6F-1D8B-46F9-AD61-DC3DF378417D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$080595CA-FBC5-4CA8-BCE2-CE7D3E08B733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43cf9d5caa2176d8dfeeda391f600a829f71722a","datavalue":{"value":{"entity-type":"item","numeric-id":4228028,"id":"Q4228028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$E0151415-0B36-4A76-B27D-F38C77696177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7ea7f5b51c55c8afbfb8f73dbd9102622b2eea4","datavalue":{"value":{"entity-type":"item","numeric-id":757241,"id":"Q757241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$A65E890B-BB66-42B2-B5EF-95EB98E840F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4def438d8a28321802a44dbba53d7d9b373961a","datavalue":{"value":{"entity-type":"item","numeric-id":3923934,"id":"Q3923934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$64441AD2-335A-41CC-8BD7-1EBDD7BBA350","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":"Q1612006$8C393F9E-1461-45C0-998B-E24F61F25CFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99f8804c468bdbb5e2217d191593253bde681e52","datavalue":{"value":{"entity-type":"item","numeric-id":4227351,"id":"Q4227351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612006$8BE63AA4-ACAB-4562-AC93-6F732B9206C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3908f5f1e5b4deb425c1c17e2dcd06a0d104b27","datavalue":{"value":{"entity-type":"item","numeric-id":2934479,"id":"Q2934479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a015fa43d16ab0ebb68d9bca54b99ef7c91583f7","datavalue":{"value":{"amount":"+0.8166422843933105","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":"Q1612006$9CC4D86E-8B3E-4CB9-BADE-FB6415B703B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"620e09955e534d4c6c7d277b703807ffe51579ac","datavalue":{"value":{"entity-type":"item","numeric-id":1814791,"id":"Q1814791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb81f5ba6aa1d681dd5ff1454eecd0941212b766","datavalue":{"value":{"amount":"+0.8022586703300476","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":"Q1612006$2526D55F-B1CE-4EC9-8A99-7DA1B7222C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d39dddaac7eb4d593af8c7000264b8770fb014c4","datavalue":{"value":{"entity-type":"item","numeric-id":922950,"id":"Q922950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6da2831784f2eceabf361c8ebdb720d66c065ee","datavalue":{"value":{"amount":"+0.7811720371246338","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":"Q1612006$37AE723A-A677-4613-BEFD-A31B333277DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b301dab50abfacf814f81ed45a34b34290636432","datavalue":{"value":{"entity-type":"item","numeric-id":1779688,"id":"Q1779688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"388fddbc3013268ce943e6f880b81f715ee1ef5b","datavalue":{"value":{"amount":"+0.777303159236908","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":"Q1612006$F4EE489F-02E7-4760-B9BB-72E6FE604BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a9dd52b166f89d4a3eedd69b7208150c915cf7c","datavalue":{"value":{"entity-type":"item","numeric-id":1612007,"id":"Q1612007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b78b57c2c6e175a724d4d63a3e4f57c7d0d07a0f","datavalue":{"value":{"amount":"+0.7756778597831726","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":"Q1612006$4207DC2F-826F-441E-9B77-C3ABB6679BAF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Totally tight Chvatal-Gomory cuts","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Totally_tight_Chvatal-Gomory_cuts"}}}}}