= Fractional row bound for quadratic knapsack
{title2=$q_i=\max\{\sum_{j\ne i}p_{ij}y_j:\sum_{j\ne i}w_jy_j\leq B-w_i,\ 0\leq y_j\leq1\}$}
= Fractional row bounds for quadratic knapsack
{synonym}
Conditioning on selecting item $i$ leaves capacity $B-w_i$. Its <fractional knapsack problem> bounds that item's total interaction with the other selected items. Thus the ordered-pair quadratic objective is at most $\sum_i(v_i+q_i)x_i$. Remove overweight items before defining their residual-capacity problems.
Back to article page
