0
$\begingroup$

Is there a known variant of the LP relaxation of a knapsack problem with possibly negative objective coefficients and weights on items, as well as an equality constraint? (e.g. in the below formulation, $w,c$ may be negative). $$ \max \sum_{i=1}^n x_i c_i \text{ s.t. } \sum_{i =1}^n x_i w_i = 0, 0\leq x_i \leq 1, \forall i = 1...\vert n \vert $$ The dual admits an easy algorithm for computing the optimal value but I'm curious if there's an algorithm for this as a known variant as that might be more informative about structure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.