Index Selection Problem
The Index Selection Problem (ISP) is a phase of fundamental importance
in the physical
design of databases, calling for a set of indexes to be built in
a database
so as to minimize the overall execution time for a given database
workload. The problem is a generalization of the well-known Uncapacitated
Facility Location Problem (UFLP). In one
paper,
we formulate ISP as a
set packing problem, showing that our mathematical model contains all
the clique inequalities, and describe a branch-and-cut
algorithm based on the separation of odd-hole inequalities.
In another
paper,
we describe an effective
exact separation procedure for a suitably-defined family of lifted
odd-hole inequalities, obtained by applying a Chvatal-Gomory
derivation to the clique inequalities.
Our analysis goes in the direction of determining a new class of
inequalities over which efficient separation is possible,
rather than introducing 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 results on two different classes
of instances are given, showing the effectiveness of the new approach.
We also test our algorithm on UFLP instances both taken from the
literature and randomly generated.
My contributions with A. Caprara are:
A Branch-and-Cut Algorithm for a Generalization of the
Uncapacitated Facility Location Problem
Trabajos de Operativa (TOP) 4/1 (1996) 135-163.
Separating Lifted Odd-Hole Inequalities
to Solve the Index Selection Problem
Discrete Applied Mathematics 92 (1999) 111-134.