Efficiently Solving the Exact Cover Problem in OpenMP

Abstract: The exact cover problem is an NP-complete problem with many widespread use cases such as crew scheduling, railway scheduling, benchmarking as well as having applications in set theory. Existing algorithms can be slow when dealing with large datasets however. To solve this problem in a quick manner this thesis uses a new method based on an existing algorithm called Algorithm X utilizing parallelization with the task construct of OpenMP to produce better results, at best providing a speedup of 4.5 when compared to a serial optimized implementation of Algorithm X. Since creating child tasks through the task construct causes additional overhead this thesis examines the effect granularity has on the solver by varying how many child tasks should be created before opting to solve the rest of the problem serially. The optimal number of child tasks is found to be very low when using a high amount of cores and vice versa when using fewer cores. Since the new method created for this thesis can solve the exact cover problem faster than Algorithm X it can prove to be beneficial when solving the problems mentioned earlier.