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