## DIMACS TR: 2005-12

## Generating All Minimal Integral Solutions to AND-OR Systems of Monotone
Inequalities: Conjunctions are Easier than Disjunctions

### Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan

**
ABSTRACT
**

We consider monotone $\vee, \wedge$-formulae $\phi$ of $m$ atoms, each of which
is a monotone inequality of the form
$f_i(x)\geq t_i$ over the integers, where for $i=1,\ldots,m$, $f_i:\ZZ^n\mapsto\
RR$ is a given monotone function and $t_i$ is
a given threshold. We show that if the $\vee$-degree of $\phi$ is bounded by a c
onstant, then for linear, transversal and
polymatroid monotone inequalities all minimal integer vectors satisfying $\phi$
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 di
sjunctive programming, data mining, matroid
and reliability theory.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-12.ps.gz

DIMACS Home Page