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

## 1 Answer

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.

• Thank you for your answer. TBH, I am not solving an LP. I am solving a very hard non-convex problem. But, my constraints are linear. Therefore, reducing is very important to me. The heuristic paper you shared says LP, I hope it works for linear contsraints as well. – independentvariable Jun 2 '19 at 13:43
• Yes, it looks for the objective as well :\ – independentvariable Jun 2 '19 at 13:45
• 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