Abstract
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
n
↦
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.