The Simple Plant Location Problem with Order (SPLPO) is a variant of the Simple Plant Location Problem (SPLP) where the customers have preferences over the facilities that will serve them. In ...particular, customers define their preferences by ranking each of the potential facilities from the most preferred to the least preferred. Even though the SPLP has been widely studied in the literature, the SPLPO, which is a harder model to deal with, has been studied much less and the size of instances that can be solved is very limited. In this article, we study a Lagrangian relaxation of the SPLPO model and we show that some properties previously studied and exploited to develop efficient SPLP solution procedures can be extended for their use in solving the SPLPO. We propose a heuristic method that takes a Lagrangian relaxation solution as the starting point of a semi-Lagrangian relaxation algorithm. Finally, we include some computational studies to illustrate the good performance of this method, which quite often ends with the optimal solution.
This paper is addressed to the generalization of simple plant location problem where customer’s preferences are taken into account. Some basic polyhedral studies and a new family of facet-defining ...inequalities are given. The effectiveness of the proposed approach is illustrated by the computational experience.
We consider a multi-echelon location–distribution problem arising from an actual application in fast delivery service. We present and compare two formulations for this problem: an arc-based model and ...a path-based model. We show that the linear programming (LP) relaxation of the path-based model provides a better bound than the LP relaxation of the arc-based model. We also compare the so-called binary relaxations of the models, which are obtained by relaxing the integrality constraints for the general integer variables, but not for the 0–1 variables. We show that the binary relaxations of the two models always provide the same bound, but that the path-based binary relaxation appears preferable from a computational point of view, since it can be reformulated as an equivalent simple plant location problem (SPLP), for which several efficient algorithms exist. We also show that the LP relaxation of this SPLP reformulation provides a better bound than the LP relaxation of the path-based model.
One of the most important distinctions that must be made in clustering research is the difference between models (or problems) and the methods for solving those problems. Nowhere is this more evident ...than with the evaluation of the popular affinity propagation algorithm (apcluster.m), which is a MATLAB implementation of a neural clustering method that has received significant attention in the biological sciences and other disciplines. Several authors have undertaken comparisons of apcluster.m with methods designed for models that fall within the class of uncapacitated facility location problems (UFLPs). These comparative models include the
p
-center (or
K
-center) model and, more importantly, the
p
-median (or
K
-median) model. The results across studies are conflicting and clouded by the fact that, although similar, the optimization model underlying apcluster.m is slightly different from the
p
-median model and appreciably different from the
p
center model. In this paper, we clarify that apcluster.m is actually a heuristic for a ‘maximization version’ of another model in the class of UFLPs, which is known as the simple plant location problem (SPLP). An exact method for the SPLP is described, and the apcluster.m program is compared to a fast heuristic procedure (sasplp.m) in both a simulation experiment and across numerous datasets from the literature. Although the exact method is the preferred approach when computationally feasible, both apcluster.m and sasplp.m are efficient and effective heuristic approaches, with the latter slightly outperforming the former in most instances.
The variable neighborhood search metaheuristic is applied to the primal simple plant-location problem and to a reduced dual obtained by exploiting the complementary slackness conditions. This leads ...to (i) heuristic resolution of (metric) instances with uniform fixed costs, up to n =15,000 users, and m = n potential locations for facilities with an error not exceeding 0.04%; (ii) exact solution of such instances with up to m = n =7,000; and (iii) exact solutions of instances with variable fixed costs and up to m = n =15,000.
In this paper we deal with a pseudo-Boolean representation of the simple plant location problem. We define instances of this problem that are equivalent, in the sense that each feasible solution has ...the same goal function value in all such instances. We further define a collection of polytopes whose union describes the set of instances equivalent to a given instance. We use the concept of equivalence to develop a method by which we can extend the set of instances that we can solve using our knowledge of polynomially solvable special cases.
This paper studies the duality gap in the simple plant location problem, and presents general formulas for the gap when certain complementary slackness conditions are satisfied. We show that the ...duality gap derived by Erlenkotter A dual-based procedure for uncapacitated facility location, Operations Research 26 (1978) 992–1009, and which has been widely used in the literature, is a special case of the formulas presented here. A counterexample demonstrates that an underlying assumption in Erlenkotter may be violated. The results may be used to obtain improved lower bounds for branch-and-bound algorithms.
The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 ...facility sites and customers. Computational results are presented and compared to dual based algorithms.
In this paper a new formulation of the simple plant location problem (SPLP) is given that uses the style of Sharma and Sharma (European Journal of Operational Research, 122(3), 37–48). When the ...integer restrictions are relaxed, it results in a new relaxation of SPLP that is different from the already well known "strong" and "weak" relaxation of SPLP. It is shown that the bound given by the new relaxation is worse than the bound given by "strong relaxation" of SPLP. However, a numerical example illustrates that the bound given by the new relaxation can at times be better than the bound given by "weak relaxation" (already known) of SPLP. In this paper a new proof which is different from the one given by Bilde and Krarup (Annals of Discrete Mathematics, 1, 79–97) is given to establish relative strengths of various relaxations of SPLP.
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., in Discrete Location Theory, Wiley-Interscience, New York, 1990, p. 119) and also, in recent times, to problems related to electronic business (refer to Fourer and Goux, Interfaces 31 (2001) 130). 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.
PDF
