Skip to content

Branch and Bound Algorithm for the 0/1 Knapsack Problem using Lagrangian Relaxation

License

Notifications You must be signed in to change notification settings

shah314/knapsack

Repository files navigation

Branch and Bound for the 0/1 Knapsack Problem

DOI

Shalin Shah

A Java implementation of the branch and bound algorithm for the 0/1 knapsack problem. The code uses Lagrangian relaxation to prune the search tree. It uses best first search. The Lagrangian multipliers are computed using coordinate ascent in an iterative algorithm.

A sample instance of 5000 items is included. This instance has the weights in weights.txt and values (profits) in values.txt. The file solution.txt contains some information about the problem instance. The algorithm is quite fast and takes less than a second to solve the 5000 instance (depends on the constraint though).

Compile and Run:
javac *.java
java BranchAndBound
Change the following in Constants.java:
  DATA_FILE_WEIGHTS
  DATA_FILE_VALUES
  DELIMITER
  MAX_WEIGHT
  NUMBER_OBJECTS

Cite this code:

@misc{shah2014bknapsack,
  title={Branch and Bound for the 0/1 Knapsack Problem using Lagrangian Relaxation},
  author={Shah, Shalin},
  year={2014}
}

Other instances are available here.

(The code is written in an old version of Java but compiles and runs fine.)