Advanced

Binary Integer Programming in associative data models

Odenbrand, Daniel LU and Fagerberg, Nils (2016) In LU-CS-EX 2016-36 EDA920 20161
Department of Computer Science
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
Odenbrand, Daniel LU and Fagerberg, Nils
supervisor
organization
course
EDA920 20161
year
type
H3 - Professional qualifications (4 Years - )
subject
keywords
Integer Programming, Gurobi, Microsoft Solver Foundation, Simplex Method, Qlik Sense, Implicit Enumeration
publication/series
LU-CS-EX 2016-36
report number
LU-CS-EX 2016-36
ISSN
1650-2884
language
English
id
8889485
date added to LUP
2016-08-29 13:30:32
date last changed
2016-08-29 13:30:32
@misc{8889485,
  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.},
  author       = {Odenbrand, Daniel and Fagerberg, Nils},
  issn         = {1650-2884},
  keyword      = {Integer Programming,Gurobi,Microsoft Solver Foundation,Simplex Method,Qlik Sense,Implicit Enumeration},
  language     = {eng},
  note         = {Student Paper},
  series       = {LU-CS-EX 2016-36},
  title        = {Binary Integer Programming in associative data models},
  year         = {2016},
}