12
$\begingroup$

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

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jun 2, 2019 at 13:43
  • $\begingroup$ Yes, it looks for the objective as well :\ $\endgroup$ Jun 2, 2019 at 13:45
  • $\begingroup$ 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.. $\endgroup$ Jun 2, 2019 at 13:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.