Generating all minimal integral solutions to ANDOR systems of monotone inequalities: Conjunctions are simpler than disjunctions ?
We consider monotone ?,? ? , ? -formulae ? ? of m m atoms, each of which is a monotone inequality of the form fi(x)?ti f i ( x ) ? t i over the integers, where for i=1,,m i = 1 ,  , m , fi:Zn?R f i : Z n ? R is a given monotone function and ti 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 m inequalities is NP-hard when m m is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.
dualization hypergraph transversals generation algorithms monotone systems of inequalities linear inequalities transversal inequalities polymatroid inequalities