# Minimal subset of rows that generate smaller polyhedron

Given a matrix $$[A|B]$$ I want to find a minimal matrix $$[A'|B'] \subseteq [A|B]$$ (i.e. the rows in $$[A'|B']$$ are also in $$[A|B]$$) such that $$A'x < B' \Rightarrow Ax < B$$.

Geometrically, I want to discard the half-planes $$X_i$$ which contain the intersection of rest of the half-planes i.e. $$X_i \supseteq \cup_{j \neq i} X_j$$.

For now my solution is, for each row in $$[A|B]$$, flip the sign (i.e., multiply by $$-1$$) and check if the new $$[A''|B'']$$ is infeasible. If it is, that row is discarded, otherwise it is kept. This would take $$n$$ calls to a LP solver, on inputs of size $$[A|B]$$, where $$n$$ is the number of rows in $$[A|B]$$. Is there a more efficient way to do this?

• If this is a practical question, do you have any information about how many rows you expect there to be in $[A|B]$ and how many in $[A'|B']$? For instance, it might be possible to come up with solutions that are more efficient if you expect that typically the minimal $[A'|B']$ will have very few rows; or typically the minimal $[A'|B']$ can be obtained by discarding only a very few rows of $[A|B]$. – D.W. Sep 21 '19 at 16:48
• I am not exactly sure. I can't tell you the trend of it, because number of rows in $[A|B]$ can be 60000 and the LP solver takes so much time to finish it. What about if $[A|B]$ is sparse. – rnbguy Sep 22 '19 at 22:41
• ah. sorry. I thought I deleted that one. it's done now. – rnbguy Sep 23 '19 at 12:13