Binary Integer Programming in associative data models

Abstract: The data visualization softwares Qlikview and Qlik Sense are based on an associative data model, and this thesis analyzes different tools and methods for solving 0-1 integer programs as well as examines their applicability to the computational engine behind these softwares. The first parts are dedicated to a theoretical background on mathematical optimization, linear programming and Qlik’s implementation of the associative data model. We tested two optimization packages, Gurobi and Microsoft Solver Foundation alongside an enumeration method we implemented in an external extension communicating with a Qlik Sense application via network. The test results showed some promise in terms of number of operations, so we created an implementation closer to the engine. While faster, using this implementation we were still unable to solve some of our more difficult problems within a reasonable time frame. An alternative heuristic for node traversal was also considered, suspecting that this would be more efficient on a different class of problems. In practice one of the heuristics, best-first search, was faster in general but we believe that it benefited from the data being autogenerated and that more optimization can be made to the alternative search method, in particular when augmenting the candidate solution. In the future, we do not believe that implicit enumeration will replace the traditional methods of solving 0-1 integer programs since Gurobi still performed the best on average, but it may have some exciting applications on a specific type of problems where, once they reach a certain size, traditional models would not stand a chance.