0
$\begingroup$

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 have $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.

EDIT to the question The matrix $Q$ is given, as well as the values of $w$. The values that I am looking for are the values of $x$ that maximize the total profit. This total profit is defined in the section Modifications I need

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ How can you have a solution before $Q$ is defined? What do you mean "appears in the solution"? For that matter, what exactly is your objective for the Graphical problem? $\endgroup$
    – Nicholas Mancuso
    Commented Mar 16, 2015 at 22:44
  • 1
    $\begingroup$ Please specify the problem precisely. Which values are given? (all the $q$'s, $c$'s, $w$'s, and $n$?) Please values are you looking to find? (all the $x$'s?) Which problem are you trying to reduce to some known problem? The one you're trying to solve, or the quadratic knapsack problem? When you say "my problem", do you mean the quadratic knapsack, or yours? Also I can't tell what you mean by "modifications I need" or what's going on in that paragraph. I'm finding it hard to understand what your question is, exactly. Please edit the question to make it a lot clearer. $\endgroup$
    – D.W. ♦
    Commented Mar 17, 2015 at 6:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.