An exact method for shrinking pivot tables. (June 2020)

• Record Type: Journal Article
• Authors: Boschetti, Marco A.; Golfarelli, Matteo; Graziani, Simone
• Is Part Of: Omega. Volume 93(2020)
• Publication Date: 2020-06
• Subjects: OLAP -- Integer linear programming -- Set partitioning -- Lagrangian relaxation -- Pricing; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2019.03.002
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: We proposed a model for the problem of shrinking pivot tables, that is a Set Partitioning Problem (SPP) with a side constraint. Solving the model by a general-purpose solver could be difficult and for some instances Cplex MIP solver fails. We proposed a new matheuristic algorithm based on a dual ascent procedure that exploits pricing and Lagrangian relaxation. We also proposed an effective exact method based on the matheuristics. The computational results show the effectiveness of proposed algorithms. Abstract: Pivot tables are one of the most popular tools for data visualization in both business and research applications. Although they are in general easy to use, their comprehensibility becomes progressively lower when the quantity of cells to be visualized increases (i.e., information flooding problem ). Pivot tables are largely adopted in OLAP, the main approach to multidimensional data analysis. To cope with the information flooding problem in OLAP, the shrink operation enables users to balance the size of query results with their approximation, exploiting the presence of multidimensional hierarchies. The only implementation of the shrink operator proposed in the literature is based on a greedy heuristic that, in many cases, is far from reaching a desired level of effectiveness. In this paper we propose a model for optimizing the implementation of the shrink operation which considers two possible problem types. The first type minimizes the loss of precision ensuring that the resulting data do not exceed the maximum allowed size. The second one minimizes the size of the resulting data ensuring that the loss of precision does not exceed a given maximum value. We model both problems as set partitioning problems with a side constraint. To solve the models we propose a dual ascent procedure based on a Lagrangian pricing approach, a Lagrangian heuristic, and an exact method. Experimental results show the effectiveness of the proposed approaches, that is compared with both the original greedy heuristic and a commercial general-purpose MIP solver.