Search code examples
knapsack-probleminteger-programming

Library for solving knapsack-prblm(integer-programming)

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.

Solution

  • 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.