Discrete optimization under constraint

Question

$\textbf{Problem:}$

Suppose the domain $\mathcal{D}$ consists of a countable set of points(finite or infinite). Let $L$ and $p$ be two nonnegative function on $\mathcal{D}$. The goal is to find a set of points, $\mathcal{I}$ such that $S = \sum\limits_{x\in\mathcal{I}} p(x)$ is minimized under the constraint that $C = \sum\limits_{x\in\mathcal{I}} L(x)p(x)$ is greater or equal to some give value $c_0$. Is there an algorithm to find such $\mathcal{I}$ given some value of $C$ without considering all possible sets?

$\textbf{Attempt:}$

My first attempt is to consider sets with bounded $L$, i.e. the sets that contain all points {$x$} such that $L(x)$ is larger than some threshold value. I will now call it bounded-$L$ set. The bounded-$L$ set is a set that fullfill the desired properties since it can be proved that we cannot decrease its $S$ without decreasing its $C$.

Therefore, each bounded-$L$ set is such an optimized set. However, not each optimised set with any given $C$ is a bounded-$L$ set. For example, we might have a bounded-$L$ set, $\mathcal{I}_{L_1}$ with $C=c_1$ and another slightly larger bounded-$L$ set, $\mathcal{I}_{L_2}$ with $C=c_2$ where $c_2>c_1$. If the given value of $C$ is $c_1$ or $c_2$, then the desired set will be $\mathcal{I}_{L_1}$ and $\mathcal{I}_{L_2}$ respectively. However, if the given $C$ is such that $c_1<c<c_2$, the situation might not be that simple.

Answer 1

If you take $L(x) = 1$ and $p(x) = x$ with $\mathcal{D} = \{a_1, \ldots, a_n\}$ then your problem could be used to solve the partition problem:

Given integers $a_1, \ldots, a_n$ find a subset $I \subset \{1, \ldots, n\}$ such that \begin{align*} \sum_{i \in I} a_i = \sum_{i \notin I} a_i \end{align*}

That is the case since you can fix $C = \frac{1}{2} \sum_{i = 1}^n a_i$ and by the choice of $L$ and $p$ it holds that $S \geq C$. Thus, the partition problem has a feasible solution if and only if your problem admits a solution with $S = C$.

Since the partition problem is NP-hard you will not find a polynomial time algorithm for your problem unless P=NP. If a pseudo-polynomial time algorithm suits your needs, you might have a look at exact algorithms solving the partition problem, though. See, for example, this paragraph of the wikipedia entry on the partition problem for such an algorithm.