Solving the three dimensional quadratic assignment problem on a computational grid

The exact resolution of large instances of combinatorial
optimization problems, such as three dimensional
quadratic assignment problem (Q3AP), is a real challenge
for grid computing. Indeed, it is necessary to reconsider the
resolution algorithms and take into account the characteristics
of such environments, especially large scale and dynamic
availability of resources, and their multi-domain administration.
In this paper, we revisit the design and implementation of
the branch and bound algorithm for solving large combinatorial
optimization problems such as Q3AP on the computational grids. Such gridification is based on new ways to effi-
ciently deal with some crucial issues, mainly dynamic adaptive
load balancing and fault tolerance. Our new approach
allowed the exact resolution on a nation-wide grid of a dif-
ficult Q3AP instance. To solve this instance, an average of
1,123 computing cores were used for less than 12 days with
a peak of around 3,427 computing cores.