# Simplest way to eliminate redundant constraints due to a new cut

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...

• mathoverflow.net/a/69667 Here they show the standard LP-procedure. Thanks to your Telgen (1977) reference I will just say that it is LP-equivalent, and here is an LP (then back to MO answer). I was wondering if my case is easier to detect somehow since I take a ball where I center $x_c$ , so maybe we can just look at the polyhedral inequalities and understand which one is redundant etc.. – independentvariable Jun 2 '19 at 13:52