C++ Implementation of Scatter Search Algotirhm as described in "The Index Selection Problem with Configurationsand Memory Limitation: A Scatter Search Approach"
Creates exectuable that solves problem instance .odbdp files. Resulting Solution is outputed as a .sol file along side a .txt file showing timeing and objective value optained during run time
Raslan Kain, Daniele Manerba, Roberto Tadei,
Computers & Operations Research, Volume 133, 2021, 105385, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2021.105385.
## Schematic representation of our Scatter Search algorithm implementation.
Abstract Abstract: Within the physical designing process of relational databases, the Index Selection Problem aims at finding the subset of indexes to build for accessing the stored information. More precisely, given a database workload, each query must be served by at most one predefined set of indexes (named configuration) to maximize the net gain in terms of time. This gain is made up of the time gain obtained to serve the queries through the configurations minus the fixed time needed to create and maintain those configurations. The clustering of indexes into configurations and the limited amount of memory available to store the indexes characterize our variant of the problem. At the same time, established approaches in the literature have only considered those two aspects separately. We model this setting as a generalization of the Uncapacitated Facility Location Problem with budget constraint and propose an Integer Linear Programming formulation for it. Then, to find near-optimal solutions in a reasonable computational time, we develop a Scatter Search meta-heuristic exploiting the specific facility location features of the problem. We test our algorithm over a broad set of benchmark instances and compare it with an exact solver and an efficient state-of-the-art heuristic method. Keywords: Physical database design; Index selection problem with configurations; Facility location problem; Memory limitation; Scatter search
obdbdp.exe i#.q#.c#.g#.m#.odbdp -t #
Where # in the .odbdp file specifies the problem instance, and # after -t is the number of seconds of run-time