Problem statement
Given a set of $N$ linear inequalities of the form $a_1x_1 + a_2x_2 + ... + a_Mx_M \geq RHS$, where $a_i$ and $RHS$ are integers. The inequality $A$ dominates or subsumes inequality $B$ if all its coefficients are less or equal and $RHS_A \geq RHS_B$. Most inequalities are sparse, i.e. most coefficients are zero. Usually, both $N > 1000$ and $M > 1000 $. I'm trying to identify dominating or subsuming inequalities efficiently.
What are quick ways to find a) if an inequality is dominated by any other inequality, and b) which inequalities are dominated by a given inequality?
(Monte-Carlo algorithms are fine, that only report correct results most of the time)
Proposed solutions in the literature
Eén, N. and Biere, A., 2005, June. Effective preprocessing in SAT through variable and clause elimination. In International conference on theory and applications of satisfiability testing (pp. 61-75). Springer, Berlin, Heidelberg. (chapter 4.2) discuss a variant of this problem in the context where all coefficients are binary, i.e. $a_i \in {0, 1}$. They propose occurrence lists, one per variable $x_i$, containing all inequalities with non-zero coefficients $a_i$. Additionally they use a hashing scheme, similar to Bloom filters, to quickly eliminate candidates. I don't see how to translate this to non-binary coefficients.
Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E. and Weninger, D., 2020. Presolve reductions in mixed integer programming. INFORMS Journal on Computing, 32(2), pp.473-506. (chapter 5.2) discuss a variant of the problem, but don't solve it. They first hash inequalities by indices of non-zero coefficients and the coefficient values. Additionally, they limit their search to a small subset of inequalities.
Schulz, S., 2013. Simple and efficient clause subsumption with feature vector indexing. In Automated Reasoning and Mathematics (pp. 45-67). Springer, Berlin, Heidelberg. describes Feature Vectors for clauses and a kd-tree-like data structure to query combinations of feature vectors.
Things I've tried
- The trivial solution is to check all pairs of inequalities in $O(n^2)$. Unfortunately, that's too slow for my application where I have millions of inequalities.
- I tried performing a random projection of the coefficients for every inequality, resulting in a projection $p_j$ for every inequality. An inequality $j$ can only dominate inequality $k$ if $p_j \leq p_k$. Thus we don't have to check all pairs. I repeat this process 10 times with multiple random projections, and use the random projection where I have to check the fewest pairs. In practice this is not effective, as most coefficients are zero - and it's unlikely that a random projection focusses exactly on the few non-zero elements. It doesn't help nearly enough.
- Similarly I implemented Feature Vectors, but couldn't replicate the performance reported by Schulz.
- AFAIK, multi-dimensional data structures break down in high-dimensional scenarios (curse of dimensionality). I'm not aware of indexing techniques that work for high-dimensional range queries.
- I thought about Bloom filters, unsuccessfully.
- I thought about randomized algorithms, unsuccessfully.
Do you have any other ideas?