Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$$$x_{ij}+x_{jk} \le 1 $$Note this problem is not the Maximum Weighted  Matching problem as edges that share the same end point are allowed.
Is the following optimization problem NP-hard?
cc.complexity theory;graph algorithms;np hardness;optimization;linear programming
The new version of the problem is indeed NP-hard.Reduction from set cover: Subsets are $S_1, S_2, ..., S_m$ and the universe is $U = \{ a_1, a_2, ..., a_n \}$. Construct a node-weighted directed graph $(N,S,c)$ as follows:Nodes are $N = \{ a_1, a_2, ..., a_n, S_1, S_2, ..., S_m, S'_1, S'_2, ..., S'_m \}$.Edges are: $(a_j,S_i)$ iff $a_j \in S_i$, and $(S_i,S'_i)$ for all $i$.Weights are: $w(a_j) = M$ for all $j$, and $w(S_i) = 1$ and $w(S'_i) = 0$ for all $i$.Now if there is a set cover $X$ of size at most $k$, we can get the benefit of at least $nM + m - k$ as follows:For each $a_j$ pick one set $S_i \in X$ in the cover with $a_j \in S_i$, and choose the edge $(a_j,S_i)$; we get the benefit of $M$ from $a_j$.For each $S_i \notin X$ we choose the edge $(S_i, S'_i)$; we get the benefit of $1$ from $S_i$.Conversely, if we can get the benefit of at least $nM + m - k$, then we have at most $k$ nodes in $\{S_1, S_2, ..., S_m\}$ and all of the nodes in $U$ must have outgoing edges; this gives a set cover of size at most $k$.