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)

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.

- 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?