Maximizing the Sum of a Subset with Excluding pairs
Your problem is known as maximum-weight independent set (more often, simply maximum independent set). We think of the $x_i$ as vertices in a graph, each constraint corresponding to an edge $(x_i,x_j)$. An independent set is a set of vertices with no edges, which is exactly your condition.

Unfortunately, maximum-weight independent set is NP-complete, and $n^{1-\epsilon}$-hard to approximate (for every $\epsilon&gt;0$) even when all weights are the same.