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.


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.