{"entities":{"Q1361003":{"pageid":1371742,"ns":120,"title":"Item:Q1361003","lastrevid":46559526,"modified":"2025-12-25T00:59:27Z","type":"item","id":"Q1361003","labels":{"en":{"language":"en","value":"Truncated Gr\u00f6bner bases for integer programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1038371"}},"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":"Q1361003$2596FEDB-FA9C-40D7-BE13-55E23617036C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"542fcf14c26be1f0ffa0b0181b1b958a6cb3bc94","datavalue":{"value":{"text":"Truncated Gr\u00f6bner bases for integer programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1361003$1D681B95-3DF2-4920-A797-FED11E96CDF2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2bf6036ceb88fb7d82c3dfdc806899bccfd61863","datavalue":{"value":"0914.90203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361003$5BD19987-D454-4D78-B07B-D2F23F52B422","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e71b1a810c94176f33b214acd409208085d409e4","datavalue":{"value":{"entity-type":"item","numeric-id":162945,"id":"Q162945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361003$0AFB8867-EAD5-445A-8756-F949C1C20617","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"db47c0d885e17d8d9a9e07c31f9d292923ca3c4b","datavalue":{"value":{"time":"+1999-06-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1361003$67846039-1885-4A04-9D0B-AD45EF351EBB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5dcd0b729d74f75ae4a43beb533802d596b95125","datavalue":{"value":"Considered is an integer program of the form: minimize \\(\\{cx\\mid Ax=b\\), \\(x\\in {\\mathbb{N}}^n\\}\\), denoted by \\(IP_{A,b,c,=}\\), where \\(A:=(a_1,\\dots,a_n)\\in {\\mathbb{Z}}^{ d\\times n}\\) is an integer matrix of full rank, \\(b\\) is an element of \\({\\mathbb{Z}}^d\\) and \\(c\\) is a vector in \\({\\mathbb{R}}^n\\) (called cost vector). \\textit{P. Conti} and \\textit{C. Traverso} [in: Applied algebra, algebraic algorithms and error-correcting codes, Proc. 9th Int. Symp., AAECC-9, Lect. Notes Comput. Sci. 539, 130-139 (1991; Zbl 0771.13014)] developed an algorithm for integer programming based on Gr\u00f6bner bases techniques: Indeed, if \\(I_A\\) is the toric ideal given by the kernel of the map \\(\\pi_A:k[x_1,\\dots,x_n]\\longrightarrow k[t_1^{\\pm 1},\\dots, t_d^{\\pm 1}]\\) given by \\(\\pi_A(x_i):=t^{a_i}\\), then the equation \\(Ax=b\\) can be converted into the membership and representation problems \\(t^b \\in I_A\\), which are solved with Gr\u00f6bner bases techniques.    The authors give an algorithm for solving the integer program \\(IP_{A,b,c,=}\\) for a fixed \\(b\\). They observe that in this case the computation of the whole Gr\u00f6bner basis of \\(I_A\\) is unnecessary since it contains many polynomials which are not involved in the representation of \\(t^b\\). Therefore they introduce a suitable multivariate grading on the ring of polynomials \\(k[x_1,\\dots,x_n]\\) induced by the matrix \\(A\\) in such a way that the ideal \\(I_A\\) becomes homogeneous and they develop a suitable theory of truncated Gr\u00f6bner bases which allows to stop the computations as soon as the multidegree of \\(t^b\\) is reached. Depending on \\(b\\), the truncated Gr\u00f6bner basis may be considerably smaller than the entire Gr\u00f6bner basis of \\(I_A\\) with respect to \\(c\\). Some examples complete the exposition.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361003$4CC6B6CC-EC7A-4474-B8AA-78F434F8FB4C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"80f116a1cdb08066811a19630fb4c8beca038913","datavalue":{"value":{"entity-type":"item","numeric-id":321274,"id":"Q321274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361003$39F5507D-3DD8-42E9-BC67-41F071C84201","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361003$B2853E7F-1232-4206-888C-71739FADB439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"173b0c3afec7c4f9f987722665cc7bdb6b8f5813","datavalue":{"value":"13P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361003$D09812F0-2517-4517-99DE-397F2D8BAB4B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0994cd8e75b9bd6fa1086d246530a3c0841078c0","datavalue":{"value":"1038371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361003$EE1DB194-8BCF-4D6A-AFA1-055EE4019ACD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361003$FABCA6E4-5C08-41C6-B147-54D67C95E082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bf2e504c06e2a8b1bdb6cf1e722423006c532a4","datavalue":{"value":"toric ideal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361003$0474EE0F-32E3-4F07-B029-F82A1F9D2BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdd0da4370edbfdaf577ea9e742ec895e54309c4","datavalue":{"value":"truncated Gr\u00f6bner bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361003$A2A04D28-792F-4088-B3E7-4875A380D9FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f3ce3e63ec8d09c68f311c3d629fb26e95ed226","datavalue":{"value":"truncated Buchberger algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361003$43315DC8-476B-4F74-82DA-9410F77A1BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d662d88706df5dc3496a0bdaaacc9d88afa268d5","datavalue":{"value":"multivariate grading","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361003$15D129DD-086C-4354-B178-DFDEF7666F54","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"414721610c0f1f33a6fdc0309e029d67d9b5a2fe","datavalue":{"value":{"entity-type":"item","numeric-id":246427,"id":"Q246427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361003$35E29730-E569-4D24-9B1B-37B5BAA8EFCA","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":"Q1361003$D971D37D-5077-457C-9B9B-83B596B1ABF4","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"cf51e68896b7351200d646212e41d565da458e0e","datavalue":{"value":{"entity-type":"item","numeric-id":20936,"id":"Q20936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361003$3ABEB5D4-0CA8-4EB3-B2CC-464D165EBECD","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":"Q1361003$118ACEC3-7E38-4443-B480-101C8CD0C485","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"05cbcd5c2ff4cb90179584ae790bebc4040379b2","datavalue":{"value":"https://doi.org/10.1007/s002000050062","type":"string"},"datatype":"url"},"type":"statement","id":"Q1361003$6654CDA9-91B9-434F-BC66-9A3228E03AA3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"290b174fb79571270c9705a3394400dd82bb9a03","datavalue":{"value":"W2135307914","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361003$8B70320F-5BAC-4819-869D-47EFA6035D19","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2fe38bd6ee20f5730bb37af47c187002e69c44f1","datavalue":{"value":"Q114852529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361003$DB598F05-70A8-4F24-9979-9D648C1180ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b48e86dca0c503913014327702f0c236b10a7337","datavalue":{"value":"10.1007/S002000050062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361003$2D9B8B5F-8A21-42ED-B491-411F9B146DFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cdf5fb83c72e8f9c279c694e588440a9b4bc63a","datavalue":{"value":{"entity-type":"item","numeric-id":5101421,"id":"Q5101421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7005f1f0e7024d7c9ab66cd7e37fb723fc6c6648","datavalue":{"value":{"amount":"+0.8550240993499756","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":"Q1361003$8E4F189C-DA49-4885-920D-6D1D456E0968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02c16dc589216e1382ec6820d8df6fc7e08bcd22","datavalue":{"value":{"entity-type":"item","numeric-id":4394952,"id":"Q4394952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f46de22b736cb5cdeed3e7cf2e7d132249f9fb11","datavalue":{"value":{"amount":"+0.84245765209198","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":"Q1361003$A0319DF3-8C28-4266-AF84-736267514E9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8c93f6cd5bcb8fe2770e17219e70a5d333dc85d","datavalue":{"value":{"entity-type":"item","numeric-id":4238963,"id":"Q4238963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2720d3b5e06381b230445f6bb57f89f9b4490004","datavalue":{"value":{"amount":"+0.8319143056869507","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":"Q1361003$0D44704D-DD70-43EE-8EC1-B764DE2758FE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1361003","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1361003"}}}}}