I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm.


I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). These constraints designate the domain for variable $x$. Imagine I have one new constraint $cx\le d$, which may or may not further constrain the original domain.
Now I can modify the right hand side of the original domain with variable $y$, $0\leq y \leq b$. The problem is to find $y$ such that $$Ax\le b-y$$ makes sure that the domains $Ax\le b-y$ and $Ax\le b-y \cup cx\leq d$ are the same (so in other words that adding a new constraint $cx\leq d$ does not change the domain. In fact I want to find minimal $y$ (for instance minimum of $\sum\_{i} y\_i$) that provides this feature.



Adding linear constraint to the domain
By LP duality, the new constraint $cx \le d$ is redundant iff there exists $u \ge 0$ such that
\begin{align}
u A &= c \tag1\label1 \\
u (b - y) &\le d \tag2\label2
\end{align}
To see the easy direction of the iff, note that \eqref{1} and \eqref{2} imply
$$cx = u A x \le u (b - y) \le d$$
You want to minimize $\sum\_i y\_i$ subject to \eqref{1}, \eqref{2} and $0 \le y \le b$, and this is a quadratically constrained linear programming (QCLP) problem.


