The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at ...the minimum cost. This problem often appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present two techniques that enhance the performance of branch and bound algorithms. The new algorithms thus obtained are called branch and peg algorithms, where pegging refers to fixing values of variables at each subproblem in the branch and bound tree, and is distinct from variable fixing during the branching process. We present exhaustive computational experiments which show that the new algorithms generate less than 60% of the number of subproblems generated by branch and bound algorithms, and in certain cases require less than 10% of the execution times required by branch and bound algorithms.
Scope and purpose
Locational decision problems of choosing the location of facilities to satisfy the demand of a set of clients at minimum costs constitute a very important class of practical problems. The simple plant location problem is a subclass of such problems, in which the facilities are supposed to have infinite capacities. These problems are used to model, among others, bank account location problems and in cluster analysis (refer, for example, to Cornuejols et al. 1) and also, in recent times, to problems related to electronic business (refer to Fourer and Goux
2). Not only are these problems important in themselves, but they also appear as subproblems in a much wider class of combinatorial problems, for example in crew scheduling, vehicle despatching, assortment, etc. The simple plant location problem is
NP
-hard and there is much research on good algorithms for these problems. Effective solution techniques based on branch and bound algorithms have been suggested in the literature. In this paper we suggest techniques that substantially reduce the execution times of such algorithms. We think that these techniques can be used to enhance the performance of almost all the available solution algorithms for this problem. We hope that this paper will motivate research to apply the techniques suggested here to other problems.
An important generalization of the traveling salesman problem called the traveling purchaser problem is considered. A branch and bound algorithm which solves a related simple plant location problem ...for calculating the bounds is proposed for this problem. Computational experiments with this algorithm provide the evidence that moderate size problems of upto 25 cities and 100 commodities can be solved in reasonable computation time. The problem is shown to have applications in the areas of scheduling, warehousing and routing.
The Data Correcting Algorithm is a branch and bound type algorithm in which the data of a given problem instance is `corrected' at each branching in such a way that the new instance will be as close ...as possible to a polynomially solvable instance and the result satisfies an acceptable accuracy (the difference between optimal and current solution). In this paper the data correcting algorithm is applied to determining exact and approximate optimal solutions to the simple plant location problem. Implementations of the algorithm are based on a pseudo-Boolean representation of the goal function of this problem, and a new reduction rule. We study the efficiency of the data correcting approach using two different bounds, the Khachaturov-Minoux bound and the Erlenkotter bound. We present computational results on several benchmark instances, which confirm the efficiency of the data-correcting approach.
An interactive modeling approach is developed to solve the practical problem of bus route network design. Possible bus routes are identified with facilities which can be` "located". Zones or pairs of ...zones in the urban area are identified with customers who will be "allocated" to the established facilities. It is shown that the classical Set Covering Problem is useful under the assumption of fixed demand; the Simple Plant Location Problem is effective under the assumption of demand which is sensitive to the level of bus service provided.
This paper treats the file redundancy issue in distributed database systems, asking what is the optimal number of file copies, given the ratio r of the frequency of update requests to the frequency ...of all file access requests (i.e., queries and updates). Formulations of this type of problem, including optimal file allocation, have been attempted by a number of authors, and some algorithms have been proposed. Although such algorithms can be used to solve particular problems, it seems difficult to draw general conclusions applicable to a wide variety of practical distributed database systems. To probe into this hard to formulate but interesting problem, our paper constructs simplified network models of distributed database systems, and computes the optimal number of file copies, as well as their locations, to minimize the communication cost. For several network types, we plot the optimal number of file copies as a function of the ratio r.
PDF
