Knapsack LP Formulation
A student proposes a 0/1-LP for knapsack using decision variables $y_i \in \{0,1\}$, constraint $\sum_i \text{weight}(x_i) y_i \le W$, and objective $\min \sum_i \text{value}(x_i) y_i$. Determine whether this correctly models knapsack.
Does this 0/1-linear program correctly model the knapsack problem?
Solution:
Correct option: No, but if we maximize the objective function instead of minimizing it, we get a correct 0/1-LP formulation of the knapsack problem.