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

We consider monotone image-formulae image of image atoms, each of which is a monotone inequality of the form image over the integers, where for image, image is a given monotone function and image is a given threshold. We show that if the image-degree of image is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying image can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of image inequalities is NP-hard when image is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.