{"entities":{"Q1424281":{"pageid":1435021,"ns":120,"title":"Item:Q1424281","lastrevid":68671062,"modified":"2026-04-13T01:19:36Z","type":"item","id":"Q1424281","labels":{"en":{"language":"en","value":"Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2055175"}},"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":"Q1424281$BD34B84B-5AA6-4949-AA5D-DBD2BD74A294","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8531cf96be80c15bde2df55e6ddb32af55631578","datavalue":{"value":{"text":"Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1424281$4525F489-EEC0-4D66-A987-CD49E699F854","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b9533076fe01f527d3cfee52aab4f82167b529f9","datavalue":{"value":"1047.90033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424281$8420847E-E6FF-4743-A57E-2CB14B6050D5","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":"Q1424281$AFB361BD-A759-40E4-B5D6-0510857EA246","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":"Q1424281$7F15AA2A-8ADE-4224-8308-CAEECD22A3A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a3e85a63ec1b4b13f2415a44b8831caa5cbedb3f","datavalue":{"value":"In order to describe the facets of a high dimensional polytope, an effective approach consists of reducing the number of variables (by fixing some of them at specified values), hoping to obtain a polytope for which at least one nontrivial inequality is obtained. The idea of lifting, introduced by \\textit{R. E. Gomory} [Linear Algebra Appl. 2, 451-558 (1969; Zbl 0184.23103)], is to use such inequalities to subsequently generate facets of higher dimensional polytopes. The paper under review develops theory and algorithms for the lifting of continuous variables for the mixed 0-1 knapsack polytope  \\[ PS=\\text{conv} \\left \\{ \\, (x,y) \\in \\{0,1 \\}^m \\times [0,1]^n : \\sum _{j=1}^m a_jx_j+\\sum _{i=1}^n b_i y_i\\leq d\\,\\right \\}, \\]  where \\(m>0\\), \\(n>0\\), \\(a_j\\), \\(b_i\\), \\(d\\) are integers. Strong robust cuts for 0-1 mixed integer programming are derived by exploiting the boundedness of and the presence of more than one continuous variable in \\(PS\\). A first original result implies that it is almost always sufficient to fix continuous variables at 0 or 1. Next it is proved that the lifting coefficients of the continuous variables fixed at 0 are almost always zero. Moreover, it is possible to completely specify the lifting coefficients for variables lifted from 0. A similar study of the lifting from 1, although much more difficult, leads to a pseudo-polynomial algorithm performing this task.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1424281$18E042B7-1182-408F-AF0D-8862F1E0F0E7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e399d6aefd0456742c9468269315b44887e7fe50","datavalue":{"value":{"entity-type":"item","numeric-id":429755,"id":"Q429755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424281$BC12976D-49D8-46D1-ADC7-14F868142C42","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424281$B8D841F8-A861-42D1-AC5D-1478A7536630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424281$0A5C7F35-D5FE-4A71-96B8-986AED4B8C36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424281$ADF05BEC-2924-4D8B-9CD7-A0B2E27D7691","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ec5f12f509c6c4e0ecdff9b6330affb6953ad413","datavalue":{"value":"2055175","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424281$1E7A5392-3E49-48BB-AF04-9D2658658295","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"446ec1f50c931e6f0ce9d6622a30474753218fe9","datavalue":{"value":"0-1 mixed integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1424281$7D74E9F6-D4D0-403E-AD4A-F00B94389846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c162d92b244f46ccc5ab4927c2f941587cfbdce","datavalue":{"value":"polyhedral theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1424281$E26811F1-E593-46BE-84B2-1B20E0CD09C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d1e0bc81013a06dddbed06be9e327564214a46e","datavalue":{"value":"lifting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1424281$2BD95A4C-EC3D-41E6-89E3-F8BB080DCE39","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"00ddba85e25e49edb35f0c4dc8c3b39cc1462297","datavalue":{"value":{"entity-type":"item","numeric-id":330265,"id":"Q330265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424281$56C5843C-9E53-4FCE-A70A-D1F217B3E75D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b01281c4adf63631b814b0abb3f40a75c493705","datavalue":{"value":{"entity-type":"item","numeric-id":378089,"id":"Q378089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424281$F2E6B9C5-3BD0-496E-B213-B04973C5D9A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1c26346d40b730bc09009d003fb3565eb0646e5","datavalue":{"value":{"entity-type":"item","numeric-id":163009,"id":"Q163009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1424281$7C0B6DA7-9474-4F1E-863D-DBE3A2E87581","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":"Q1424281$80DEAD67-6469-4DA2-8E90-88542C0010B0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5822e4971e4ceb94ee28e0f076105726632b468e","datavalue":{"value":"https://doi.org/10.1007/s10107-003-0398-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1424281$EFAA6DAB-B5E5-4E4C-BD21-2D9529A657D1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"12e2fb9a03bfaba07760808fd4b32fc9fa5308df","datavalue":{"value":"W2112538451","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424281$89E7F0E5-E565-467E-9997-5629D247B762","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d38812b0d88ca0b4964ca84d5b973d688eaaf314","datavalue":{"value":"10.1007/S10107-003-0398-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1424281$39183FC2-C38D-473D-A7FA-06CCAAC51664","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41771a93f955f21c9b4ecf80f821e7283074f74f","datavalue":{"value":{"entity-type":"item","numeric-id":4737525,"id":"Q4737525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01ceb6d40e1b1357d41cd1f079979667b3fc2c48","datavalue":{"value":{"amount":"+0.8599311","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$3ECD82D3-2840-46A0-AA8C-884AFFEAC032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df5811809f22b24050640471eefe47f18c3d6b8f","datavalue":{"value":{"entity-type":"item","numeric-id":1424282,"id":"Q1424282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e754a2474fbe49d074bec6734c15e52e2ee2d298","datavalue":{"value":{"amount":"+0.8235496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$F6212719-E39F-4DCC-95E4-874BB1ACB72C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8e56eef952307f48cd36d113558a5498672aa32","datavalue":{"value":{"entity-type":"item","numeric-id":4667214,"id":"Q4667214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae268cf5e9325430087209e1a3eb402e420b7735","datavalue":{"value":{"amount":"+0.8184246","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$AA56B324-EE86-476C-B35C-654B32AE1CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4a7cbc90c7fc472b08b9c73c4d5bf59a0203126","datavalue":{"value":{"entity-type":"item","numeric-id":1890949,"id":"Q1890949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66dc0570ceb34881768787e46b91305756324935","datavalue":{"value":{"amount":"+0.8143734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$3E67239B-1A30-42D4-9A2B-5360BBADEB29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9328ace464b49ee20178636957d3b4b59f9ae413","datavalue":{"value":{"entity-type":"item","numeric-id":1295954,"id":"Q1295954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f55edbf90d2e462eeb299314996ccd312a3024c","datavalue":{"value":{"amount":"+0.796798","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$7473F9B9-9B08-4D31-9D6E-904C28CBCA36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90d34ef175cf3275a90a45c3f6634538ae642259","datavalue":{"value":{"entity-type":"item","numeric-id":847822,"id":"Q847822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfc6bc08860eee2c5064255091fb40cba86820d4","datavalue":{"value":{"amount":"+0.7896629","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$44C55767-3923-487C-8940-6F4887E4FCD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fef57f8472025fecd5ffd78628522c21c064a41","datavalue":{"value":{"entity-type":"item","numeric-id":3032082,"id":"Q3032082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a0fbfb8e2358eb49df6741ae72f497e960498a7","datavalue":{"value":{"amount":"+0.78033406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$850A557A-B4DB-4C8A-9EF4-B17C4661085E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea53d7252cdb53c94471030384fa589fe0153f46","datavalue":{"value":{"entity-type":"item","numeric-id":2899134,"id":"Q2899134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cee307bfeb4d0235e8a7e058e85f13c41e0188a","datavalue":{"value":{"amount":"+0.7759209","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$86D56A9A-46B6-4656-90A8-DDF389993B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"151eacd3f93e60d992b44451c612fb8d91209802","datavalue":{"value":{"entity-type":"item","numeric-id":5920488,"id":"Q5920488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21a5e5feeda68d81405f8c7af168fb85714ed2f6","datavalue":{"value":{"amount":"+0.77572006","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$E3B3EBDC-7B68-48D1-A444-AA37EB69BED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cdd5927bf210707f017d0626e7dd6b91c3ce0e4","datavalue":{"value":{"entity-type":"item","numeric-id":2462108,"id":"Q2462108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12a74e21f6f5811753be215428de96d7b90958ea","datavalue":{"value":{"amount":"+0.7734297","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1424281$F3D8CC22-95C5-46C4-90E7-AB84ACC0418B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lifted_inequalities_for_0-1_mixed_integer_programming:_Basic_theory_and_algorithms"}}}}}