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

We consider monotone ∨, ∧-formulae φ of m atoms, each of which is a monotone inequality of the form f_i (x) ≥ t_i over the integers, where for i = 1, ..., m, f_i : Zⁿ {mapping} R is a given monotone function and t_i 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 m inequalities is NP-hard when m is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.