{"entities":{"Q2627629":{"pageid":2638372,"ns":120,"title":"Item:Q2627629","lastrevid":52819325,"modified":"2026-01-23T14:00:39Z","type":"item","id":"Q2627629","labels":{"en":{"language":"en","value":"Merging valid inequalities over the multiple knapsack polyhedron"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6724885"}},"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":"Q2627629$6B13AB0B-17C5-4492-A9D3-338B8337A6DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3146b2f39633051b3a1797a0b039e2b6a27665cf","datavalue":{"value":{"text":"Merging valid inequalities over the multiple knapsack polyhedron","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2627629$74FDAD7A-5840-40F6-B910-DB3EE342C1E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d902433c1a4f2dd86567e4863c7553941a951da","datavalue":{"value":"1362.90297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627629$7F28B84B-2FBD-44B4-B512-BB6B36F6006D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"88df4c687dab1ceea8eefb231a991d799a905fc9","datavalue":{"value":"10.1504/IJOR.2015.071495","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627629$59EAEFCC-940F-4E0B-8AA4-7727C03678E8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7968e38c276bf5f2b6ba4e8eb4d4411dc496fdfb","datavalue":{"value":{"entity-type":"item","numeric-id":1958256,"id":"Q1958256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627629$A773D26E-A41F-4AB3-BA80-83BE6979EF47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"81214bfc166d3a4acc4b2165db164730da40f1b0","datavalue":{"value":{"entity-type":"item","numeric-id":684155,"id":"Q684155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627629$8A538D1C-6511-490E-AE1A-2173D60450F5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627629$ED79E8EC-7020-424A-8C22-292D9E71762C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d49858a0afe4b614990a77fa152712e1ae2b828","datavalue":{"value":{"time":"+2017-05-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2627629$5BF79687-F9C2-4DF1-8DEA-FADA5F970418","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8163669070303c3f02a7fae2f4a486ac3061e596","datavalue":{"value":"Summary: This paper provides the theoretical foundations for generating a new class of valid inequalities for integer programming problems through inequality merging. The inequality merging technique combines two low dimensional inequalities of a multiple knapsack problem, potentially yielding a valid inequality of higher dimension. The paper describes theoretical conditions for validity of the merged inequality and shows that the validity of a merged cover inequality may be verified in quadratic time. Conditions under which a valid merged inequality is facet defining are also presented. The technique is demonstrated through a multiple knapsack example. The example also demonstrates that inequality merging yields a new class of valid inequalities that are fundamentally different from other known techniques.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627629$D5024363-9EDA-47C7-A92A-B62B6B6693FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627629$57AB77B0-4639-4289-B77D-E594C9A9F523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627629$E677C9F2-EDED-48FC-835E-5E7DCB3CF1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627629$14710042-B4FC-4977-A022-5F4F453DC1B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"df166825f50aa83b1ca11b47dba20d4bb5515a66","datavalue":{"value":"6724885","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627629$880B4B5C-A163-46F4-888D-76E74EF47574","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627629$749C0539-DF54-4ADA-84BB-C3802C503FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c3967bed412c2d760afda0f357673824e161b8c","datavalue":{"value":"inequality merging","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627629$85D11CBA-F108-4E2D-8C36-632AF4CA02F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"716dac1111922ad89f28f3f7f9fca3441a4dfa26","datavalue":{"value":"valid inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627629$9E807CF5-A29E-44D0-8DFC-E9A69852356A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7959e1b788b49d33cb497776b899055fed13cec","datavalue":{"value":"multiple knapsack","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627629$50787839-E974-4664-A1F7-8AD56EF05492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c162d92b244f46ccc5ab4927c2f941587cfbdce","datavalue":{"value":"polyhedral theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627629$481788C7-2A40-46AB-A310-3FB7229AC570","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":"Q2627629$07454D1C-F9B3-4C45-98EE-0C8DFC398C79","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f929029f75b30169fbdd6a75d12b08b9d06f747","datavalue":{"value":"https://doi.org/10.1504/ijor.2015.071495","type":"string"},"datatype":"url"},"type":"statement","id":"Q2627629$CB3416C4-1596-45D5-8276-1EA64CA791CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ca529d6157ee6a9997313988ec6fb988bec54d02","datavalue":{"value":"W2102694748","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627629$57ED699E-73A5-4802-8E41-3FC00AD20D23","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"223abfe05dc1215b4fdcb457d52488aa0696d62f","datavalue":{"value":{"entity-type":"item","numeric-id":5151546,"id":"Q5151546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"054faf8c0a486178c5a6e058fde9547a29d27391","datavalue":{"value":{"amount":"+0.824596643447876","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":"Q2627629$F8454312-6B4F-432D-86DA-82E1BDD1B457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee93469093963c5727a295689272fbe6b9cd0784","datavalue":{"value":{"entity-type":"item","numeric-id":1751116,"id":"Q1751116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"862a4007a4b9945c9c4543e0c95e921fea9821cf","datavalue":{"value":{"amount":"+0.7694705128669739","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":"Q2627629$40F26CB0-ADD9-4164-ABD9-41EE139253ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0624b953d1060716fa471544f2964ea6872002c0","datavalue":{"value":{"entity-type":"item","numeric-id":2639772,"id":"Q2639772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6350ec2875d55d0569f3a1fe6d4efa73e1685264","datavalue":{"value":{"amount":"+0.7669711112976074","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":"Q2627629$99D7D6E6-D4D3-400E-9836-AC62489FD735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f604aff630be6d7f9a49461236397d2ff0766be","datavalue":{"value":{"entity-type":"item","numeric-id":5943076,"id":"Q5943076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8fd2f535dc058d60470dd37f53dbe2f7182b790","datavalue":{"value":{"amount":"+0.7641816735267639","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":"Q2627629$5858D856-CAB9-44AD-A71C-55AEE5D36E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0cc247e1bb7ee2dadae39287dcf00ce3f6ea3c0","datavalue":{"value":{"entity-type":"item","numeric-id":5477436,"id":"Q5477436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4755c491beaa0b127246ed06e95cddfea88a7e4d","datavalue":{"value":{"amount":"+0.7608176469802856","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":"Q2627629$EFD14D35-F23D-4BB1-920B-CF40D615B2D3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2627629","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2627629"}}}}}