Parallel algorithm to Bounded Knapsack Problem (matteocilk.com)

  • courseware
  • Algorithms and Complexity
  • Advanced Analysis
  • CILK++
  • C
  • branchandbound technique
  • Search
  • The included code and solution write-up provides a parallel solution for the bounded knapsack problem, as described in the included problem description text file. The included write-up gives an overview of a branch-and-bound technique (as opposed to a dynamic programming algorithm) to enumerate possible solutions. The three heuristics that are implemented in the code (linear-programming relaxation, minimum-weight heuristic, and dominator heuristic) are described. The algorithm is parallelized using Cilk++ in order to launch recursive search tasks. The code was intended for Linux OS platforms.
    DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

    Unter der Lizenz Creative Commons License stehen Downloads zur Verfügung. Jetzt herunterladen
    Einzelheiten zur Compiler-Optimierung finden Sie in unserem Optimierungshinweis.