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

| improve this answer | |
$\endgroup$
  • $\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$ – independentvariable Jun 2 '19 at 13:43
  • $\begingroup$ Yes, it looks for the objective as well :\ $\endgroup$ – independentvariable Jun 2 '19 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$ – independentvariable Jun 2 '19 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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