Project Topics
Get Complete Project Material File(s) Now! »
Absolute and Vertex Restricted p-Center Problems
The absolute 1-center problem is initially de ned by Hakimi [4] and solved using graphical methods by taking advantage of the piecewise linearity of the function f(X) on any edge fk; mg 2 E, that is, X is a subset of the points on edge fk; mg 2 E. Piecewise linearity for the absolute 1-center problem has important consequences for p > 1 as it leads to the existence of a nite point set P G such that there exists an absolute p-center in (P [ N). This is initially observed by Minieka [2] and extended to the weighted case by Kariv and Hakimi [5]. This property is generalized later by Hooker et al. [6] to a more general setting.
Existing solution methods are either based on solving a sequence of set cover-ing problems or enumerating p-element subsets of J. The rst set-covering based approach is proposed by Minieka [2] for the absolute p-center problem. Minieka [2] presents a systematic method to update the set covering matrix to converge to an optimal solution in a nite number of steps. At each step the set covering problem is solved for the updated matrix corresponding to a smaller distance value selected from the distinct distance values set R and the algorithm is ter-minated when the optimal value of the set covering problem is greater than p. Christo des and Viola [7] solve the weighted absolute p-center problem by rst generating regions in the network. A region is a set of points (a single point or an edge segment) that can reach the same set of vertices within radius r. Then, a bipartite graph is constructed in the following form. The original nodes are put on one side, the regions are put on the other side, and there is an edge between a node and a region if the node is reachable by that region. Finally, they nd a minimal covering of the constructed bipartite graph. This approach does not make use of the nite distance set R, instead it proposes increasing the radius value by a small increment at each iteration. Toregas et al. [8] solve the vertex restricted p-center problem by solving a linear programming relaxation of the associated set covering problem and adding a cut in case of fractional solutions. Gar nkel et al. [9] solve the absolute p-center problem by solving a sequence of set covering problems but they rst reduce the search space by nding a heuris-tic solution X and eliminating from J all those points whose relative radii are greater than f(X). They apply two types of tests to eliminate some of the inter-section points and standard matrix reductions and heuristic techniques to reduce the number of rows and columns of the set covering matrix. Their method can be extended to the weighted p-center problem as well. Sac [10] implements a new set covering based algorithm for solving the absolute p-center problem. In this algorithm, both the construction of the set covering problems used and the generation of the intersection points di er from the traditional methods in the literature. The new algorithm is compared with the classical set covering based binary search algorithm on problems with up to 900 nodes and better solution times are observed with the new method.
Daskin [11] gives the rst IP formulation of the vertex restricted p-center problem but prefers to use a set covering based bisection search over an interval de ned by pre-computed lower and upper bounds on rV . Daskin [12] improves this algorithm by solving, via Lagrangean relaxation, a maximal covering location problem in which the total number of vertices that are covered within r is maxi-mized while the number of open facilities is restricted to p. Ilhan and Pinar [13] propose a two phase extension of Daskin’s [11] algorithm for the vertex restricted problem. In the rst phase, several LP relaxations of the set covering problem are solved as feasibility problems by forcing the objective value to be less than or equal to p to nd an appropriate lower bound on rV . In the second phase, several set covering problems with the same restriction on the objective value are solved by systematically changing the radius value starting from this lower bound. Al-khedhairi and Salhi [14] propose some modi cations to the algorithms in [11] and [13]. Elloumi et al. [1] propose a di erent IP formulation for the p-center problem. They give a lower bound which is tighter than the LP relaxations of both models in the literature and a polynomial time method to compute it via solving a sequence of LPs. They solve the p-center problem by performing a bi-nary search over the ordered list of distinct values of distances that are between their proposed lower and upper bounds. A set covering problem is solved for each selected distance value between the bounds. They solve problems from the OR-Library [15] and TSPLIB [16] with up to 1817 nodes using binary search. To our knowledge, this is the largest network size solved in the literature.
We note here that the term \bisection search » refers to successively halving a real interval and discarding either the lower or the upper half in each step until its size is smaller than a predetermined positive real number whereas the term \binary search » refers to performing essentially the same operation on a nite list of numbers using a median element of the list.
Kariv and Hakimi [5] prove that the weighted p-center problem is NP-Hard even if the network G is planar with unit vertex weights, unit edge lengths and with the maximum vertex degree of 3. They provide enumeration based algo-rithms for the weighted and unweighted p-center problem for p = 1 and p > 1 on general and tree networks. The computational complexities of these algorithms are O(jEjn log n) for the weighted absolute 1-center, O(jE jn + n2 log n) for the unweighted absolute 1-center, O(jEjp(n2p 1)=(p 1)! log n) for the weighted ab-solute p-center, and O(jEjp(n2p 1)=(p 1)!) for the unweighted absolute p-center problems on general networks. Moreno [17] provides another enumeration based algorithm for the weighted p-center problem with better computational complex-ity of O(jEjpnp+1 log n). Later, Tamir [18] provides improved complexity bounds for the weighted and unweighted p-center problems by combining the algorithms of [5] and [17]. The improved bounds are O(npjEjp log2 n) and O(np 1jEjp log3 n) for the weighted and unweighted problems, respectively.
There are several studies that focus on solving special cases of the p-center problem such as 1-center problem and p-center problem on tree networks. Gold-man [19] comes up with a localization theorem for the absolute 1-center problem. This theorem results in a very e cient polynomial algorithm for the tree net-works and after this pioneering study, tree networks have received considerable attention. Handler [20] proves that the absolute center of a tree is the midpoint of a longest path in the tree when all nodes have unit weight and provides a poly-nomial algorithm for nding the absolute center of a tree. Hal n [21] proposes a modi cation for the algorithm of [19]. Dearing and Francis [22] study weighted absolute 1-center problem on both tree and general networks. Hakimi et al. [23] study weighted cases of absolute 1-center and absolute p-center problems on tree networks. Low order polynomial time algorithms for solving the p-center problem on tree networks are provided by [5], [24], [25], [26], [27], [28]. Another study on the absolute 1-center problem by [29] proposes an improvement on the algorithm of [4]. The improvement is proposed on nding the best candidate point on an edge. The proposed method nds the best candidate point by using only the shortest path distance values between node pairs and does not require the knowl-edge of point-vertex distance function. Recently, Dvir and Handler [30] propose a new algorithm for solving absolute 1-center problem on general networks.
Capacitated p-Center Problem
The rst study on the capacitated p-center problem is by Bar-Ilan et al. [53]. They study the the p-center problem where a facility can serve at most L demand nodes. They refer to this problem as the balanced p-center problem and this is a special case of the problem that we study where each node has a demand of one unit and each facility has a capacity of L units. They provide an approximation algorithm with an approximation factor of 10. Khuller and Sussmann [54] study the same problem and provide an approximation algorithm with an approxima-tion factor of 6. They also study a simpli ed version of this problem, in which more than one center can be placed on a node. They call this problem as the capacitated multi-p-center problem and propose a 5-approximation algorithm for it. Cygan et al. [55] focus on the same problem but with non-identical capac-ities, that is, the capacities of the facilities are not identical. They prove that there exits a constant factor approximation algorithm for this problem; they do not give the exact constant, but state that it is in the order of hundreds. They also provide an 11-approximation algorithm for the capacitated p-center problem with non-uniform capacities when more than one center can be placed on a node. Their algorithm uses an LP rounding technique. Jaeger and Goldberg [56] pro-vide a polynomial time algorithm for the capacitated p-center problem on trees with identical capacities. Scaparra et al. [57] present a large-scale neighborhood search heuristic for the capacitated p-center problem. Although they also present a mixed integer programming (MIP) formulation for the problem, they focus on their heuristic algorithm and solve problems with up to 402 nodes by using this algorithm. In addition to the mathematical model in [57] there are only two studies that attempt to solve the capacitated p-center problem optimally. The rst one is due to Ozsoy and P nar [58]. They provide an exact algorithm, which is a modi cation and adaption to the capacitated case of the 2-Phase algorithm in [13] proposed for the uncapacitated p-center problem. In this algorithm, the capacitated concentrator location problem and the bin-packing problem are used as sub-problems. In the rst phase of the algorithm, the LP relaxation of the capacitated concentrator location problem is solved for di erent radius values iteratively and a lower bound for the optimal value of the capacitated p-center problem is obtained. In the second phase of the algorithm either the capacitated concentrator location problem or the bin-packing problem is solved initially for the smallest distance value which is greater than or equal to the lower bound. The objective value of the sub-problem gives the number of facilities to be opened to satisfy capacities for the given radius value. Therefore, if the optimal value obtained from the sub-problem is greater than p, the sub-problem is solved for the next smallest distance value which is larger than the current distance value. This procedure is repeated until the smallest distance value that provides an optimal value that is less than or equal to p is achieved. They solve problems with up to 402 nodes optimally. They also present a MIP formulation for the capacitated p-center problem, but they do not provide any computational study on this model.
Contribution of the Thesis Work
In this thesis, we initially focus on the vertex restricted p-center problem. We provide a new mathematical formulation and a new method based on successive restrictions of the new formulation. We obtain a new integer programming model with better linear programming (LP) bounds by tightening one set of constraints in our model. A semi relaxation of our proposed model gives the tightest known lower bound, which is obtained earlier by Elloumi et al. [1], and we present a polynomial time algorithm to compute this bound. Additionally, we propose new lower and upper bounds, which are within a constant multiple of the optimal value of the problem and can be obtained via polynomial time algorithms. We conduct experiments on weighted and unweighted benchmark problems from OR-Library [15] and TSPLIB [16] with up to 3038 nodes by using a specialization of our method, referred to as double bound algorithm. We solve the problems that require large amount of time by integrating the reduction rules to our algorithm and observe signi cant improvements in utilization of the reduction rules. As our methods are applicable to both vertex restricted and absolute p-center problems, we focus on solving the absolute p-center problem by using the double bound method. We devise new theoretical results for the absolute p-center problem and use these results to develop a new method for generating the intersection points. We solve problems from OR-Library [15] with up to 900 nodes and 16056 edges. In addition to the double bound method, we develop another exact algorithm based on the Benders Decomposition method to solve the p-center problem. We compare the performances of the Benders algorithm and the double bound al-gorithm on problems from OR-Library [15]. In addition to the uncapacitated p-center problem, we focus on the capacitated p-center problem. For the single allocation capacitated p-center problem, we propose new mathematical formula-tions and a new exact algorithm that solves the uncapacitated p-center problem and an allocation problem successively. We refer to this algorithm as \successive p-center-allocation algorithm » and this algorithm di ers from the approaches in the literature since we decompose the problem into two di erent and relatively easier problems and solve them iteratively to obtain the optimal solution for the capacitated p-center problem. Moreover, this thesis focuses on the multiple al-location capacitated p-center problem for the rst time in the literature. The formulations and the successive p-center-allocation algorithm that we propose for the single allocation capacitated p-center problem are readily applicable to the multiple allocation capacitated p-center problem. Additionally, we propose a branch and cut algorithm based on a non-compact formulation obtained through projection for solving the multiple allocation capacitated p-center problem. We conduct large scale experiments by using our algorithms and solve problems with up to 900 nodes and 1291 nodes for single and multiple allocation capacitated p-center problems, respectively. The dimensions of problems we solve in this thesis are signi cantly higher than the ones reported in the literature.
Relaxation and Heuristic Bounds
Before solving P3, if we know that there exists a set S R such that the optimal value of the p-center problem is di erent from any j 2 S, we can e ectively use this information: we remove these values from R and drop associated zj variables from the model, thus, decrease the size of the problem to be solved. For example, if we have a lower bound LB on the optimal objective value, then we may remove any j < LB from R; similarly, if we have an upper bound U B, then we may remove any j > U B and solve the model with the restricted R and obtain an optimal solution. In this section, we rst analyze the LP relaxation bounds of the four models discussed in this chapter. Then, we propose a tighter bound obtained from a partial relaxation of our formulation P3. In addition to the lower bounds that we obtain from relaxations, we propose new lower and upper bounds that can be obtained e ciently.
Table of contents :
1 Introduction
2 Notation and Denitions
3 Literature Review
3.1 Absolute and Vertex Restricted p-Center Problems
3.2 Capacitated p-Center Problem
3.3 Contribution of the Thesis Work
4 The Vertex Restricted p-Center Problem
4.1 Mathematical Formulations Existing in the Literature
4.2 Proposed Formulations
4.3 Relaxation and Heuristic Bounds
4.3.1 LP Relaxations
4.3.2 Semi Relaxations
4.3.3 Attaining Quick Lower and Upper Bounds
4.4 Double Bound Algorithms
4.5 Computational Experiments
4.5.1 Unweighted Problems
4.5.2 Weighted Problems
4.6 Conclusion
5 Absolute p-Center Problem
5.1 Generation of the Intersection Points
5.2 Improved Lower and Upper Bounds
5.3 Computational Experiments
6 Single Allocation Capacitated p-Center Problem
6.1 Proposed Formulations
6.2 Successive p-Center-Allocation Algorithm
6.3 Computational Experiments
6.4 Conclusion
7 A Branch and Cut Algorithm for Solving the Multiple Allocation Capacitated p-Center Problem
7.1 Proposed Formulations
7.2 A Branch and Cut Algorithm
7.3 Computational Experiments
8 Conclusions and Future Research Directions
8.1 Preliminary Results of a Benders Decomposition Algorithm for Solving the p-Center Problem
8.2 Contribution Summary
8.3 Future Research Directions
