Införandet av allmänna avvikelser av formen "πx ≤ π 0  på πx ≥ π 0 + 1", där π, π 0 är heltal värderas, är en grundläggande operation i både gren-och-bundet och skärplan algoritmer för att lösa blandade heltal linjära program. Sådana avvikelser kan användas för förgrening vid varje iteration av den grenbundna algoritmen eller för att generera delade ojämlikheter för skärplanets algoritm. Vi överväger först problemet med att välja en allmän disjunktion och visar att problemet med att välja en optimal sådan disjunktion, enligt specifika kriterier som beskrivs häri, är N P-hård. Vi visar vidare att problemet fortfarande N P-hård även för binära program eller när man överväger vissa begränsade klasser av disjunktioner. Vi konstaterar att problemet med att avgöra om en given ojämlikhet är en delad ojämlikhet kan minskas till ett av de ovan nämnda problemen, vilket leder till ett bevis på att problemet är N P-fullständigt.
På den teoretiska sidan visade Mahajan och Ralphs att problemet med att hitta en allmän disjunktion med maximal objektiv vinst är N P-hård REF.
On the Complexity of Selecting Disjunctions in Integer Programming
{'venue': 'SIAM Journal on Optimization', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}