1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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, 2019 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, 2019 at 22:41
  • $\begingroup$ ah. sorry. I thought I deleted that one. it's done now. $\endgroup$
    – rnbguy
    Sep 23, 2019 at 12:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.