A dual-ascent procedure for the file allocation and join site selection problem on a telecommunications network

In this paper, a model and a solution procedure is developed for the File A llocation and Join Site Selection Problem with 2-way Join [FAJSP-2], define d on a telecommunications network. This problem attempts to integrate the f ile allocation and query optimization aspects of a distributed computing sy stem. By allowing for queries that require processing up to two file types, this problem is designed to determine simultaneously the number and locati on of file types and the location of join operations. This problem is model ed as a mixed-integer linear program, for which a fast dual-ascent approxim ation procedure is developed. Extensive computational results are presented which demonstrate that our dual-ascent procedure is able to solve even lar ge-scale problems to near optimality quickly. (C) 1999 John Wiley & Sons, I nc.