Describe usage in the README.md

1 files changed, 91 insertions, 1 deletions

diff --git a/README.md b/README.md
index 710be19..a5bea81 100644
--- a/README.md
+++ b/README.md
@@ -1,2 +1,92 @@
 # knapsack-solver
-0/1 knapsack problem solver.
+This is command-line utility for solving 0/1 knapsack problem
+usingbranch-and-bound method, dynamic programming, simple heuristic
+(weight/price)and fully polynomial time approximation scheme. It can measure
+CPU andwall-clock time spent by solving a problem, compute relative error of
+theresult and generate graphs from those values.
+
+## Usage
+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 files
+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.
+
+### Output files
+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 Brand and Bound
+method and ```size_4.dataset``` input dataset file the following files are
+produced:
+```
+size_4_branch_and_bound.results
+size_4_branch_and_bound.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
+```
+
+### Graphs
+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.
+
+## RubyGems
+This knapsack problem solver is published as a Gem at RubyGems.
+https://rubygems.org/gems/knapsack_solver
+
+## License
+This project is licensed under the MIT License - see the [LICENSE](LICENSE)
+file for details.