Find dominated or subsumed linear inequalities efficiently

Question

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?

Answer 1

Unfortunately there is a nearly-quadratic-time lower bound that may prove a barrier. In particular, you can't solve it in $O(N^{2-\varepsilon})$ time for any $\varepsilon>0$ unless the Strong Exponential Time Hypothesis is false. In particular, the special case where all coefficients are 0 or 1 and the RHS is the same for all inequalities is equivalent to searching a bunch of sets for a pair that have a subset relationship, and that is hard: see https://cstheory.stackexchange.com/q/9896/5038.

The one saving grace is that this lower bound is for arbitrary sets, i.e., it does not take into account sparsity. It is possible that you might be able to use sparsity somehow to do better than the general case.

Here is an algorithm that takes advantage of sparsity to do a bit better. Suppose that every inequality has only $K$ nonzero coefficients. Form a balanced binary tree on the $N$ inequalities. Annotate each node with a map that maps $x_i$ to the max of all coefficients of $x_i$ in all inequalities under that node. Now given an inequality $A$, you can check whether it dominates any other inequality by traversing the tree in a top-down breadthfirst fashion. Any time you hit a node that maps $x_i$ to something smaller than $x_i$'s coefficient in $A$, there is no need to visit any of the children of that node, and traversal of that subtree can be skipped. Heuristically, I expect you'll probably need to visit $O(KN/M)$ nodes of the tree on average (well, plus $O(\lg N)$ to account for the fact that each inequality dominates itself, but I'll ignore that as it seems likely to be small in comparison to the other terms). Creating the tree takes $O(NK)$ time, and visiting each node takes $O(K)$ time, so I expect the overall running time per inequality will be something like $O(KN + K^2N/M)$, on average. Since you have $N$ inequalities, the total time should be something like $O(KN + K^2N^2/M)$. I don't know whether this is any better than what you already have in mind, though.