1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.