Separating lifted odd-hole inequalities to solve the index selection problem

The Index Selection Problem (ISP) is a phase of fundamental importance in t he physical design of databases, calling for a set of indexes to be built i n a database so as to minimize the overall execution time for a given datab ase workload. The problem is a generalization of the well-known Uncapacitat ed Facility Location Problem (UFLP). In an earlier publication [A. Caprara, J.J. Salazar Gonzalez, TOP 4 (1996) 135-163], we formulate ISP as a set pa cking problem, showing that our mathematical model contains all the clique inequalities, and describe a branch-and-cut algorithm based on the separati on of odd-hole inequalities. In this paper, we describe an effective exact separation procedure for a suitably-defined family of lifted odd-hole inequ alities, obtained by applying a Chvatal-Gomory derivation to the clique ine qualities. Our analysis goes in the direction of determining a new class of inequalities over which efficient separation is possible, rather than intr oducing new classes of (facet-defining) inequalities that later turn out to be difficult to separate. Our separation procedure is embedded within our branch-and-cut algorithm for the exact solution of ISP. Computational resul ts on two different classes of instances are given, showing the effectivene ss of the new approach. We also test our algorithm on UFLP instances both t aken from the literature and randomly generated. (C) 1999 Elsevier Science B.V. All rights reserved.