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?

  • $\begingroup$ 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]$. $\endgroup$ – D.W. Sep 21 '19 at 16:48
  • $\begingroup$ 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. $\endgroup$ – rnbguy Sep 22 '19 at 22:41
  • $\begingroup$ ah. sorry. I thought I deleted that one. it's done now. $\endgroup$ – rnbguy Sep 23 '19 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.