This repository was made to preserve the work done on the master's degree of Henrique Becker. Created as a backup and an effort for the sake of repeatability in computer science.

The theme of the master's degree of Henrique Becker is the Unbounded Knapsack Problem, specially algorithms that solve hard UKP instances fast (without the use of parallelization), and the relationship of the UKP with BPP/CSP (Bin Packing Problem/Cutting Stock Problem) when BPP/CSP is solved by the column generation approach.


  • codes - Contain diverse algorithm implementations in diverse languages. The name of the subfolders is given by the programming language used.
    • codes/cpp - Most relevant folder. Where the state-of-art implementations are. See the inside the folder for more information.
    • codes/hs - Haskell code. Used to replicate algorithms that need the lazy evaluation provided by some functional languages.
    • codes/ocaml - Ocaml code. None written by Henrique Becker because he doesn't know the language. Used to store backups of the PYAsUKP (main article here).
    • codes/ocaml/pyasukp_site.tgz - Code taken from the pyasukp site cited above. Crashed for some instances.
    • codes/ocaml/pyasukp_mail.tgz - Code received by e-mail from Poirriez (12 jan 2016). Doesn't crash as the first one crashed.
    • codes/rb - Ruby code. Used to prototype things and create scripts too complex for BASH.
    • codes/sh - Bash code. Used to make scripts.
    • codes/r - R code. Used to generate graphs and charts.
  • latex - The tex sources of all degree-related texts.
  • data - Data gathered from the executing codes on the 'codes' folder over instances (probably the instances were created by scripts on codes/sh that makes use of the code in codes/ocaml).
    • data/ukp - Sample instances from here.
    • data/sukp - Sample instances on a format very similar to ".ukp" but slight simplified.
    • data/tukp - Sample instances as R tables and the items that make part of an optimal solution of those instances.
    • data/charts - Charts used to study some UKP instances (that are too big to store in this repo).
    • data/easy_ukp - Sample instances for very slow algorithms/implementations.
    • cplex.script & - Sample code for remembering how to execute things in cplex (".lp" files not provided to not bloat repo size, can be generated using codes/rb/gen_ukp_model.rb together with glpsol/GLPK).
    • data/results - Very important folder. Contains the info of many benchmarks done (spreadsheets with the times and memory use).
    • data/results/pyasukp_paper_bench - Probably the most important benchmark until now. Executed over 4540 instances generated by the scripts on codes/sh/pyasukp_paper_bench (the instances generated by the scripts should be the same as the ones used on the benchmark, already generated instances are too big to store in the repo, the pyasukp command used by the scripts is from codes/ocaml/pyasukp_site.tgz).