Library for solving knapsack-prblm(integer-programming)

Question

I am trying to solve the knapsack-problem, which is also an integer-programming problem. I have looked at several approximate solutions like dynamic-programming, greedy algorithm, branch-and-bound algorithm, genetic algorithms. Can you tell me a library(in any language) that helps implementing any/all of these algorithms?

Thanks in advance.

Answer 1

Here are a few implementations of the Knapsack Problem (KP):

• CPLEX If you are familiar with CPLEX (IBM) they have a page for Knapsack (among many other IP formulations) here.
• Java: They also have a Java implementaion of the knapsack problem here. (look specifically at javaknapsack.mod)
• Python: Here's one example of multiple solution techniques of the Knapsack problem.(by Dave Eppstein)
• CPP: Here's a Genetic Algorithm implementation of the KP.

A simple web-search should get you many more examples because the knapsack problem is easy to solve (and to teach) using several of the techniques you mention.