Generating all minimal integral solutions to AND–OR systems of monotone inequalities: Conjunctions are simpler than disjunctions

We consider monotone ∨,∧∨,∧-formulae φφ of mm atoms, each of which is a monotone inequality of the form fi(x)⩾tifi(x)⩾ti over the integers, where for i=1,…,mi=1,…,m, fi:Zn↦Rfi:Zn↦R is a given monotone function and titi is a given threshold. We show that if the ∨∨-degree of φφ is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying φφ can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of mm inequalities is NP-hard when mm is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.