{"entities":{"Q1424275":{"pageid":1435015,"ns":120,"title":"Item:Q1424275","lastrevid":68671014,"modified":"2026-04-13T01:19:35Z","type":"item","id":"Q1424275","labels":{"en":{"language":"en","value":"Cyclic group and knapsack facets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2055170"}},"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":"Q1424275$BBF3D227-A5AF-4FA4-8443-3FB19F375E8D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"66e0b1fb87421b6e858fcc3001e9fd1756691750","datavalue":{"value":{"text":"Cyclic group and knapsack facets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1424275$0712153F-8C2E-4F5A-ACEF-15BF45C4836C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51c1ce36abceab6c16d94b3f933e84d2a4e321de","datavalue":{"value":"1082.90094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$5975659F-D4F4-4E8C-BEEE-0A2E443542E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5af0b802ef24b09e80ea95833d7b5a78ea281321","datavalue":{"value":{"entity-type":"item","numeric-id":1041928,"id":"Q1041928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424275$467CE479-1D66-46F3-BEF2-503E1C48B423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b01e7b4165a097b7d50c5ff38dc111e651debc50","datavalue":{"value":{"entity-type":"item","numeric-id":1424272,"id":"Q1424272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424275$5FFC3380-E199-4F97-96AD-EBEAE20AA24E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"48f45a06cf4ca4f2e0149bfd550867afeccc0ded","datavalue":{"value":{"entity-type":"item","numeric-id":537594,"id":"Q537594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424275$11A7D349-A988-435F-8EC6-DA5EF523027A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b6d4e4678039073260fe7a4b1fc8198b13b94ab4","datavalue":{"value":{"entity-type":"item","numeric-id":210414,"id":"Q210414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424275$572D36A2-FC82-4CF2-BF92-F7DE63581E4A","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":"Q1424275$36D648E8-904E-452E-8AAF-1547C4410DCF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0b6c8851f7ca9b573a23f71c429912121ef1856e","datavalue":{"value":{"time":"+2004-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1424275$5F84A4E1-E706-4A6C-95AD-84F8D9693F8F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7ba50441919aa42219525c4fd4a276893d5654d3","datavalue":{"value":"This article considers the problem of finding facet-defining inequalities for group relaxations of knapsack problems. A group relaxation of an integer program can be found by removing the non-negativity constraints on the basic variables of its linear programming relaxation.  The article begins with an introduction to cyclic group relaxations and the master cyclic group problem for general integer programs. In the third section, a classification of cyclic group facets is presented, focusing on {mappings} and {seeds}, which are used to generate cuts (the mixed integer cut being one of them).  In sections 4 and 5 the knapsack polytope is studied, and the relationship between the master cyclic group problem and the master equality knapsack polytope is examined.  Sections 6 and 7 concentrate on knapsack and knapsack cover facets. A summary of the facets in tabular form and detailed proofs of lemmas are presented in the annexes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1424275$104929D8-387A-4FAC-9881-AC939F5A0AE2","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":"Q1424275$F9C59A09-7E33-46FD-87C4-EB01C3283D28","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$D5BF4766-45FD-4F70-8CF6-9E3A628D08B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$1F1E7B9C-28BD-4A1F-8D35-DDC217F98653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$24C77961-289D-4DE8-9EF1-FDA69D0D6768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$35909975-F658-4649-ACB7-0564D33815BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e2bec1c6ec1480a40d6d5658c901817c7c7c6837","datavalue":{"value":"2055170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$DDCBB70E-202B-4C48-A162-D19B0A916B9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0804fd1d01a82b2c4c3e3dc9d47ddf4817b9bae7","datavalue":{"value":"cyclic group facets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1424275$8995AC9D-1D93-4E9B-AE86-D0BE4021CAC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1424275$E270404E-37E1-48EF-BB51-9288F8513C09","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":"Q1424275$27548ADD-08BB-423A-B020-68AE4E8CBAA8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"48be6769041c115d325dc52fafe74d4279e1b318","datavalue":{"value":"https://doi.org/10.1007/s10107-003-0390-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1424275$45183419-DD30-406E-B8B9-A83246D2E41D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"42d5da4851ce466a8f27d116013654bd160f1a4c","datavalue":{"value":"W2073057258","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$D93A3448-42C6-4D47-A7DD-5F770F4B8FA1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"838ad4ec886f5e37e9cacb0caaa6db7ad0993950","datavalue":{"value":"Q101069343","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$28026B2B-8F3E-418D-BDFE-4CB72B0BD831","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b8f04a7eb1522c5e3f4bdec901973cfb6dbfc11a","datavalue":{"value":"10.1007/S10107-003-0390-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424275$63FC5163-AD12-4C15-A63B-36E9825F7CFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2e737b5e19a235d0a299e512c31a0d1f823c720","datavalue":{"value":{"entity-type":"item","numeric-id":5351614,"id":"Q5351614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48c51c0b60ab031d53640f7609cf1d4be6824fd1","datavalue":{"value":{"amount":"+0.78863525390625","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":"Q1424275$F7CAA556-FD8B-4418-A99D-C4E2A6CAA9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1706f6717da426d428c98ad40bc17d897398135f","datavalue":{"value":{"entity-type":"item","numeric-id":1960187,"id":"Q1960187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"970cb091bc8ad1095fdbbfe722fc7405e0d87210","datavalue":{"value":{"amount":"+0.7870842814445496","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":"Q1424275$8DC1BFEB-A94D-42F8-9339-54EAA111EE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad5960b70dc19a024d59222e885d7bef4906fa3f","datavalue":{"value":{"entity-type":"item","numeric-id":5429268,"id":"Q5429268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb8c2e590ce55bdd044e3e581cc0555ca10966f7","datavalue":{"value":{"amount":"+0.7835980653762817","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":"Q1424275$699A7FEB-B88B-420B-843A-9E8601BD9E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c71dc37cec2f1199b864192b8d329b40173c40b7","datavalue":{"value":{"entity-type":"item","numeric-id":1949270,"id":"Q1949270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80f1fa81b5f0d49c7510ab22d05b665f84c05a7b","datavalue":{"value":{"amount":"+0.7826277613639832","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":"Q1424275$C6DCA04F-5B41-4E62-A4B1-35F0E0371F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4120b28dc1d62338fd4c69bac79dd40144aa62cb","datavalue":{"value":{"entity-type":"item","numeric-id":1424283,"id":"Q1424283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd0a6312979eede31de244c2e01894b4f40617ec","datavalue":{"value":{"amount":"+0.7771890759468079","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":"Q1424275$9E62ABE1-1DF6-4D54-9DBE-2E36DF2CF126","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cyclic group and knapsack facets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Cyclic_group_and_knapsack_facets"}}}}}