Unfeasible linear program becomes feasible if a variable is removed

Question

Apologies, not a computer scientist by trade but I'm playing with linear programming these days.

Let $\{x_i\}$ be $N$ optimization variables with bounds

$$l_i \leq x_i \leq u_i$$

I'm interested in telling if $\exists$ a feasible region under the constraint

$$\sum_i x_i = C$$

for a fixed value of $C$.

This is pretty easy (just check that $\sum_i l_i \leq C \leq \sum_i u_i$). But sometime it happens that while

$$\sum_i x_i=C\,$$

is too constraining,

$$\sum_{i\notin {\mathcal{S}}} x_i =C\, , $$ has a feasible region for some subset of index $\mathcal{S}$.

But at first sight it's hard to tell because there's $N$ variables, such that a brute force check runs in $2^N$.

---

Examples: $l_x=l_y=10$, $u_x=u_y=30$ and $C=15$ is not feasible but it would be feasible if one was to remove either $x$ or $y$ from the problem.

---

Is there some elegant solution to this problem? There's a nice geometrical way of understanding the problem. In the two variable cases, removing either $x$ or $y$ amounts to projecting the region bounded by $[l_x, u_x],[l_y, u_y]$ onto $y$ or $x$ axis respectively. Then it's only a matter of asking whether the line $x+y=C$ crosses either of the "projected" regions (which are now lines).

Answer 1

There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a subset of the $u_i$ that sums to $C$ (which is the Subset Sum problem).

If your problem did not allow $l_i=u_i$, if you were to require that $l_i<x_i<u_i$, you could get around this by setting $10000\cdot l_i<x_i<10000\cdot u_i + 1$ which for sufficiently large values of $10000$ ensures that $x_i$ will be "close enough".