Simplest way to eliminate redundant constraints due to a new cut

Question

I have a polyhedral set for constraining $x$: \begin{align} \mathcal{P} = \{x \in \mathbb{R}^n_{+} : \ Dx \leq d \} \end{align} where $D \in \mathbb{R}^{m \times n}, d \in \mathbb{R}^m$. I find the Chebyshev center of this polyhedron, by solving: \begin{array}{ll} \max &\, r\\ \text{s.t.} & D_i^\top x_c + r \|D_i^\top\| \leq d_i \ \text{for }i =1,\ldots,m \end{array} Now I have this $x_c$, Chebyshev center of $\mathcal{P}.$ I split this polyhedron by two parts. Let $r \in \mathbb{R}^n$ be a random vector. I can divide $\mathcal{P}$ by two halves by adding $r^\top x_c \leq r^\top x$ or $r^\top x_c \geq r^\top x$ to have $\mathcal{P}^\geq, \mathcal{P}^{\leq}$.

Now, in this way, there are definitely new redundant constraints. I have seen some ways to find these redundant constraints, but my case is more specific since I divide based on the center. Therefore, I am wondering if there is an easy way to address this issue...

Answer 1

As a partial answer, Telgen (1977) has shown that eliminating all redundant inequalities is LP-equivalent, i.e. in general not easier than solving linear programs. Clearly, this does not exclude heuristics (e.g. A heuristic approach for identification of redundant constraints in linear programming models) or a better strategy for removing (a subset of) the redundant inequalities in your special case.

Telgen, J., On redundancy of systems of linear inequalities, Rep. 7718, Econometric Institute, Erasmus University Rotterdam, 1977.