4
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You are right. And actually upon closer inspection the bounds are actually included (edited question to reflect the change). $\endgroup$ – jgyou Oct 10 '15 at 6:57

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.