I have the following problem. I wonder whether or not it appears in the literature. Is it NP-hard?
Given a set $S = \{1,2,\ldots,m\}$, and $A_1,\ldots, A_n$ are subsets of $S$. Each set $A_i$ has an associated weight $x_i\geq 0$ (unknown). Given $c_i,\ldots,c_n$ and $s_1, \ldots,s_m$. The question is how can we choose at most $k$ numbers from $S$ such that $\sum_{i=1}^nc_ix_i$ is maximum, provided that if $j\in S$ is chosen then we must have $\sum\limits_{i: j\in A_i}x_i \leq s_j$, otherwise if $j$ is not chosen, then $x_i = 0$ for all $A_i$ contains $j$. This problem can be formulated as the following MILP. Let $y_j = 1$ if $j$ is chosen and $y_j = 0$ otherwise, then we have the following model $\max \sum_ic_ix_i$ s.t $\sum\limits_{i: j\in A_i}x_i \leq s_jy_j$ for all $j\in S, \sum_jy_j \leq k, x_i \geq 0, y_j \in \{0, 1\}$.
Thank you in advance!
Here is a reduction from clique - it's a bit trickier than it looked at first.
CLIQUE is the NP-complete language defined as the pairs $(G,c)$ where $G$ is a simple graph containing a clique of order $c$.
To reduce CLIQUE to your problem, use $S=V(G) \cup E(G)$ and take $A_{ij}=\{i,j,ij\}$ for each edge $ij$. (To match the problem description as written, use enumerations of these sets; $m=|V(G)|+|E(G)|$ and $n=|E(G)|$). Set $c_{ij}=1$ and $s_{ij}=1$ for each edge $ij$. Set $s_i=c-1$ for each vertex $i$. Set $k=c+\binom c 2$.
If there is a clique $i_1,\dots,i_c$, the set of these vertices and all the edges between them gives a set of $k$ elements of $S$. Setting $x_{ij}=1$ for edges in the clique and $x_{ij}=0$ otherwise, we find that $\max\sum_{ij}c_{ij}x_{ij}\geq \binom c 2$.
On the other hand, given a solution with $\sum_{ij}c_{ij}x_{ij}\geq\binom c 2$, there must be at least $\binom c 2$ positive values $x_{ij}$. That means there are at least $\binom c 2$ edges chosen in $S$. So the number of vertices chosen must be at most $k-\binom c 2=c$, but it also has to be at least $c$ to allow $\binom c 2$ edges. This means there is in fact a clique of order $c$ in $G$.