We know that LP can solve optimization problems that have linear constraints and linear objective functions.

A knapsack problem can be formulated into a linear objective function (because it is just a summation of Pi*Xi) and linear constraints (because it is just a summation of the items weights which should be <= the knapsack weight), so why can't we consider it an LP problem?


You can set up the knapsack problem as an integer linear program: To each item associate a 1/0 variable (include/exclude that item). Setting up the restrictions and the objective function from here is straightforward.

The point here is that the variables are restricted to be integers, while (regular) linear programming assumes real variables. They look similar, but are quite different beasts, computationally.

One successful technique to construct an approximate solution to the knapsack problem makes up a (continuous) linear programming problem, solve that one and tweaks the resulting values.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.