An Efficient Implementation of a Joint Generation Algorithm

Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property defined over the elements of $\cC$. We consider the problems of incrementally generating jointly the families $\cF_{\pi}$ and $\cI(cF_{\pi})$ of all minimal subsets satisfying property $\pi$ and all maximal subsets not satisfying property $\pi$, when $\pi$ is given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time. In this paper, we present an efficient implementation of this procedure. We present experimental results to evaluate our implementation for a number of interesting monotone properties $\pi$