This is a frozen project. It is intended to provide authentic snapshot of the history with all the good things and all the things that could be improved.

This is command-line utility for solving 0/1 knapsack problem using branch-and-bound method, dynamic programming, simple heuristic (weight/price) and fully polynomial time approximation scheme. It can measure CPU and wall-clock time spent by solving a problem, compute relative error of the result and generate graphs from those values.

It was created as a coursework from Programming in Ruby course during my studies at Faculty of Information Technology at Czech Technical University in Prague.

Built-in usage information can be obtained by executing knapsack_solver with -h or --help option.

Usage: knapsack_solver OPTIONS DATASET_FILE...
    -b, --branch-and-bound           Use branch and boung method of solving
    -d, --dynamic-programming        Use dynamic programming for solving
    -f, --fptas                      Use FPTAS for solving
    -r, --heuristic                  Use brute force method of solving
    -e, --fptas-epsilon EPS          Relative error for FPTAS from range (0,1)
    -o, --output DIR                 Directory for output log files
    -g, --graphs DIR                 Directory for graphs
    -v, --version                    Show program version
    -h, --help                       Show this help message

At least one method of solving must be selected and one input dataset file must be provided.

Dataset input file has the following format:

id
capacity price_1 weight_1 price_2 weight_2 ... price_N weight_N
...

id is non-negative integer number. It is followed by lines and each of these lines describes one instance of 0/1 knapsack problem instance. capacity is non-negative integer number and it is total weight of things that can be put into the knapsack. Capacity specification is followed by pairs of non-negative integer numbers. Each pair defines one thing that can be put into the knapsack. The must be at least one instance defined.

For each dataset and each selected method of solving two output files are produced: file with results and file with statistics. When option -o is not given, content which would be written to the files is written to stdout separated by one blank line (results are written the first and are followed by statistics). Both files have the same basename which is constructed as concatenation of input dataset file basename and method of solving. E.g. for Dynamic programming method and size_4.dataset input dataset file the following files are produced:

size_4_dynamic_programming.results
size_4_dynamic_programming.stats

The first two lines of the .results file begins with #. Those are comments. They are followed by lines with results of solving corresponding instances from the input dataset file. E.g.

# ../test/output_logs/size_4_dynamic_programming.results
# price    config    cpu_time    wall_clock_time    relative_error
65 [1, 0, 0, 0] 0.009999999999999995 0.011663347017019987 0.0
86 [0, 0, 1, 0] 0.010000000000000009 0.006198941962793469 0.0
52 [0, 0, 1, 0] 0.009999999999999995 0.012558827002067119 0.0

Relative error is added only when some exact solving method is selected (Branch and Bound or Dynamic programming). Format of the .stats file is the similar. Example:

# ../test/output_logs/size_4_dynamic_programming.stats
# avg_price    avg_cpu_time    avg_wall_clock_time    avg_relative_error
67.66666666666667 0.01 0.010140371993960192 0.0

Graps are produced by Gnuplot in the directory specified by -g option. Image format is .png. For every average value from statistics (price, cpu_time, wall_clock_time, relative_error) one graph is created. X axis values are dataset IDs. In one graph there are multiple functions plotted. One function for each selected method of solving, so that these methods can be compared.

Besides from images, for each image a Gnuplot configuration file is generated. These files have .gnuplot suffix. User can edit these files by hand to make some additional changes and generate graphs by passing the files to Gnuplot.

This knapsack problem solver is published as a Gem at RubyGems.

https://rubygems.org/gems/knapsack_solver

This project is licensed under the MIT License - see the LICENSE file for details.