The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form:
$max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$
$s.t \sum_{i=1}^n{w_ix_i} \leq c$
$x \in \{0, 1\}^n$
Where $n$ is the number of items, $c$ is the capacity (positive and integral) of the knapsack, $w_i$ are the positive and integral weights of the items and the $q_{ij}$ are the non-negative and integral profits.
I am trying to solve a problem whose closest cousin might be the quadratic knapsack problem or some other sort, but it has been difficult for me to reduce this problem to some known problem.
Modifications I need
Consider a directed acyclic graph that will describe relationships between nodes. Whenever node $i$ appears by itself, the profit will be $q_{ii}$. But if for some reason an ancestor $j$ of $i$ (as defined by the directed acyclic graph) appears in the solution together with $i$, then I need $q_{ij}=-q{jj}$. Also, if more than one ancestor of $i$ appears in the solution together with $i$, I want to only apply the discount of the ancestor of $i$ closest to $i$.
Do you have any pointers to a known problem to which I could reduce my problem? Any help would be greatly appreciated. And please, if you can put better tags to this question than the ones I placed, feel free to edit them.