# What is the name of following optimization problem and algorithms to solve them

Let $S=\{1,\ldots,n\}$ be a set and $w_i (\geq 0)$ be the weight of element $i$. Let $R_j, j = 1,\ldots,m$ be subsets of $S$, called the restriction sets. Choose elements from set $S$ to maximize total weights such that at most one element is selected from each set $R_j$. This problem can be modeled as $\max \sum_i w_ix_i$ subject to $\sum\limits_{i\in R_j}x_i \leq 1$ for all $j$ and $x_i \in \{0,1\}$.

I think this problem is well-known in literature but I have no idea what it is. Does anyone know this problem and the algorithm to solve it. Thanks

• It's clearly an instance of an integer linear program. I doubt you can do much better. – quasi Jan 29 '18 at 10:45
• The problem is closely related to the maximum weight clique problem, which is notoriously hard to approximate well, let alone solve exactly, in the worst case. In practical applications, there is often some structure that can be exploited, though. – Taneli Huuskonen Jan 29 '18 at 11:12