DIMACS TR: 2001-12

Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

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


We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that for any monotone system of $r$ linear inequalities in $n$ variables, the number of maximal infeasible integer vectors is at most $rn$ times the number of minimal integer solutions to the system. This bound is accurate up to a $polylog(r)$ factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-12.ps.gz
DIMACS Home Page