NP dur (comme KNAPSACK) - un schéma d'approximation?

Question

Pour un ensemble donné $S = \{1, 2, ... , N \}$, chaque composant $i\in S$ peut être représenté par un triple $(a_i, b_i, c_i)$. Comment résoudre les problèmes suivants? Un algorithme de temps polynomial existe-t-il?

$$\max_{S' \subseteq S} \left(\sum_{k\in S'} a_k \right) \cdot \left(\sum_{k\in S'} b_k \right) $$ sujet à $$\sum_{k\in S'} c_k \leq C. $$

Si la fonction objectif est $\sum_{k\in S'} a_k$, c'est KNAPSACK, et il existe un algorithme polynomial efficace. Je n'ai aucune idée s'il existe une méthode pour résoudre ce type de problème.

Answer 1

Vous pouvez résoudre ce problème de sac à dos quadratique via la programmation linéaire entière comme suit. Pour$i\in S$, laissez la variable de décision binaire $x_i$ indiquer si $i\in S'$. Pour$1\le i < j \le N$, laissez la variable de décision binaire $y_{i,j}$ représenter $x_i x_j$. Le problème est de maximiser $$\sum_i a_i b_i x_i + \sum_{i < j} (a_i b_j + a_j b_i)y_{i,j}$$ sous réserve de \ begin {align} y_ {i, j} & \ le x_i && \ text {pour tous$i<j$} \ tag1 \\ y_ {i, j} & \ le x_j && \ text {pour tous $i<j$} \ tag2 \\ y_ {i, j} & \ ge x_i + x_j - 1 && \ text {pour tous $i<j$} \ tag3 \\ \ sum_i c_i x_i & \ le C \ tag4 \ end {align} Si tout$a_i$ et $b_i$ sont non négatifs, vous pouvez omettre $(3)$.