P Median Problem Which Is Facility Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The p-median problem which is a facility location problem, deals with discrete data and hence it is characterized as a combinatorial optimization problem. It is NP-Hard in nature that determines the specified number of locations as facilitators which serves the maximum locations. The p-median problem will be constructive in several applications areas such as escalating marketing strategies in Management Sciences and identification of server positions in computer networks.

Location analysis is a domain of Operational Research that consists of a rich assortment of mathematical models. Roughly speaking, a problem is classified to fit in to the location field if some decision pertaining to the position of new facilities has to be made. In general, the objective or goal of the location problem is concerned with the detachment between new facilities and other components of the space where they have to be positioned. Location models can be classified into three groups: continuous models (X µ Rq), discrete models (X is finite) and network models (X is a finite union of linear and continuous sets). Another possible classification is as a median (mini-sum) or center (mini-max) problem, depending on the nature of the objective function considered. Location models are also deterministic or stochastic, linear or nonlinear, single or multi criteria, and so on.

The p-median problem is one of a superior class of problems known as minisum location-allocation problems. These problems locate medians among existing points, which is not equivalent to finding centers among points. It is a characteristic of minimax location-allocation problems. The p-center problem is an example, where the objective is to minimize the maximum distance between points and center(s). Minisum problems originated in the 17th century. In the early 20th century, Alfred Weber presented the same problem with the addition of weights on each of the three points to simulate customer demand. Finding the median point corresponded to discovering the best location for a facility to comply with the demands at the points. This problem is usually acknowledged as the first location-allocation problem. It was later generalized. Hakimi developed the absolute median and p-median to obtain the optimal location of switching center(s) in a communication network. Since his work, the p-median problem has been inseparable from location theory, becoming one of the most common facility location models.

The p-median problem is defined as an optimization problem that is well known in the Operations Research literature and has been extensively applied to, facility location. In the p-median problem facilities must be located among a given set of sites. The p-median problem can be depicted as: Let F is the set of facilities, C is the set of customers and distance function d is such that d: C x F ƒ  R. Here the distance function estimates the distance between a customer and a facility. The p-median problem determines a subset R of facilities F such that |R| = p, for any positive integer p and number of facilities n, where p ≤ n, such that the sum of the distances from each customer to its adjacent facility is minimized. In the proposed work it is assumed that every customer location can be considered as a facility i.e. F = C, and also for giving equal importance to each location it is considered that wi = 1.

Mathematically p-median problem is stated as [24]


n = number of locations

xij=1 if a location i is assigned to facility located at j,

=0 other wise

yi = 1 if j th location is a facility

= 0 other wise

dij = distance measured from location i to location j j

p = preferred number of locations as facilities

Here the first objective function minimizes the sum total of the distances between the customer locations and the preferred number of locations. The second constraint substantiates that each location is allotted to precisely one adjoining facility. The third constraint forbids the allotment of customer locations to a facility that was not preferred as a desired location. The fourth constraint depict the total number of desired locations as p and finally the fifth and sixth constraints guarantee that x and y are binary valued. As the result of the p-median problem segregate the solution space, the given space can be classified as groups and hence the p-median problem can be used as a clustering technique.

To discover the solution space of a specific optimization problem effectively several general-purpose sophisticated procedures can be instantiated. Formerly, Metaheuristics like genetic algorithms; tabu search, simulated annealing, ant systems, GRASP and others have been imparted and are applied to real-life problems in numerous areas of science [13]. To elucidate the GRASP (Greedy Randomized Adaptive Search Procedures) Metaheuristic [2, 3] several optimization problems [4] are effectively employed. The search procedure for recognizing the solution utilized by GRASP is iterative and each iteration consists of two phases: construction phase and enhancement phase. The construction phase aims to build a feasible solution, and based on the feasible solution its neighborhood is discovered in the enhancement phase to find a better solution [14][25][26]. The outcome is the principal solution originated over all iterations


O. Alp, E. Erkut, and Z. Drezner. in their paper named "An efcient genetic algorithm for the p-median problem" described a simple and fast genetic algorithm that models the indices of vertices in the solution as genes of a chromosome. The fitness function is the objective function. Whereas traditional genetic methods use a crossover approach, this technique creates a union of the parent's chromosomes, creating an infeasible solution with m > p genes. A greedy deletion heuristic is applied to decrease the number of genes until p genes are left. No mutation operator is used.

P. Avella, A. Sassano, and I. Vasil'ev presented a three step heuristic for large p-median problems in their work "A heuristic for large-scale p-median instances". First, a Lagrangian relaxation was solved by using a sub-gradient algorithm, producing a lower bound. Second, a subset of "promising" variables was selected to create a core problem. Third, branch-and-bound was run on the core problem to find an upper bound. Computational results comparing this method with the GRASP metaheuristic were presented.

K. R. Baker in his paper "A heuristic approach to locating a fixed number of facilities", Presented a heuristic based on dynamic programming concepts for the p-median problem keeping p value fixed. This is a suboptimal method concerned only with obtaining a good solution rapidly.

In the paper " Solving the p-median problem with a semi-lagrangian relaxation", C. Beltran, C. Tadonki, and J.-Ph. Vial described a semi-Lagrangian relaxation that, under certain conditions, closes the integrality gap for any linear combinatorial problem with equality constraints. This process inserts one constraint into the inner minimization problem of the maxmin problem and relaxes it to a "less than or equal to" constraint. For large enough multipliers, this relaxation closes the integrality gap. The p-median problem is easier to solve, however, when the multipliers are small. The insight here is to increase the Lagrangian multipliers but keep them small enough to keep the inner problem easy until an integer optimal solution is found. Computational results are presented, showing that this method solved to optimality several "easy" problems, and improved the best known dual bounds on several unsolved "difficult" problems. The method was able to solve to optimality one of the previously unsolved "difficult" problems.

A. Ceselli, in his paper entitled " Two exact algorithms for the capacitated p-median problem" introduced branch-and-bound and branch-and-price methods for solving the capacitated variation of the p-median problem. The branch-and-bound technique uses Lagrangian relaxation and subgradient optimization, and the branch-and-price algorithm uses column generation. The author noted that the ratio p/n strongly affects the behavior of these algorithms. The performance of the branch-and-bound technique worsened quickly as the ratio increased. The branch-and-price algorithm was found to be more stable.

An alternate p-median formulation called COndensed Balinski constraints with the Reduction of Assignment variables (COBRA) is proposed by R. L. Church in his work namely " COBRA: A new formulation of the classic p-median location problem". As the name itself suggests, this formulation is usually smaller than the classic p-median formulation of [10], reducing the number of variables by up to 60%.

T. G. Crainic, M. Gendreau, P. Hansen, et al. in their paper named "Parallel variable neighborhood search for the p-median" offered a new strategy entitled Co-operative Neighborhood VNS (CNVNS). This is a master-slave procedure where the master process initiates several VNS threads, each of which randomly chooses a neighbor- hood to explore. Threads report improved solutions to the master process in order to find an overall solution.

P. J. Densham and G. Rushton used necessary conditions of optimal p-median solutions to develop a more efficient variant of vertex substitution algorithm which is an existimg solution to p-median problem in the paper "A more efficient heuristic for solving large p-median problems". This information is used to create an informed spatial search procedure that is more efficient and more effective than the original naive spatial search procedure. This procedure is implemented in a new method called Global/Regional Interchange Algorithm (GRIA).

M. R. Garey and D. S. Johnson showed that the p-median problem is NP-hard in his work namely "A guide to the theory of NP-completeness". The authors also proposed that if p is fixed then it is solvable in polynomial time. It is also solvable in polynomial time for arbitrary p if the graph is a tree.

In the paper entitled "Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation", K. Jain and V. Vazirani discussed only the metric p-median problem, where the weighted cost Wij is a metric that satisfies the triangle inequality. They provided an approximation algorithm with an approximation guarantee of 6. The algorithm runs in O(n log n(L + log n)) time, where L is the number of bits needed to represent connecting cost.

A. A. Kuehn and M. J. Hamburger, in their work "A heuristic program for locating warehouses", introduced a greedy heuristic for the warehouse location problem that has historically been applied to the p-median problem. The summary of the work is : Let M be the set of potential warehouse locations and let N be the number of locations to evaluate at each iteration. The greedy heuristic initially chooses N locations that maximize the cost savings of replacing these N locations with warehouses. It then considers each of these locations individually and calculates the total distribution cost. Any location that does not reduce the total cost is eliminated from further consideration. The location that gives the least cost is assigned a warehouse, and any remaining locations go back to the list of possible locations to test. This process is repeated until all elements of the original list of potential warehouses have either been eliminated or assigned as a warehouse.

J.-H. Lin and J. S. Vitter dealt only with the metric p-median problem in "Approximation algorithms for geometric median problems". They presented a polynomial time algorithm that, for any ε> 0, finds a solution of no more than 2(1 + ε) times the optimal cost and of at most (1 + (1/ ε ))p median vertices.

R. E. Marsten in his work namely "An algorithm for finding almost all the medians of a network" showed that for a network of n nodes every p-median (1£ p£ n) is an extreme point of a polyhedron. He presented an algorithm that tours these extreme points. Some extreme points correspond to p-median solutions with a fractional value of p. Furthermore, the tour may not hit a p-median for every value of p. Aside from these exceptions the algorithm in the work was shown to create a complete set of medians.

E. D. Merino and J. M. P´rez presented an alternate formulation of the p-median problem and then applied a Hop field neural network model to solve it in "An efcient neural network algorithm for the p-median problem". The problem formulation involves two types of neurons, one for location and the other for allocation. The constrained formulation is turned into an unconstrained problem by introducing a penalty function that penalizes the objective function if constraints are violated. Computational results are presented comparing this method with vertex substitution

M. G. C. Resende and R. F. Werneck in their work "A hybrid heuristic for the p-median problem" introduced a randomized multistart iterative metaheuristic known as GRASP (Greedy Randomized Adaptive Search Procedure). Each iteration of this process applies a greedy randomized algorithm followed by a local search procedure. A pool of some of the best solutions of previous iterations is stored, and after each iteration, the new candidate solution is combined with one stored solution in a process called path-relinking. Once the algorithm terminates, the stored solutions are combined with each other.

C. ReVelle and R. Swain in "Central facilities location' provided the first linear programming formulation of the p-median problem. Constraint (4), described in p-median mathematical formulation is relaxed. The authors recommend using a branch-and-bound technique when dealing with fractional solutions. This formulation was tested on several problem instances and no fractional solutions occurred.

P. Avella, A. Sassano, and I. Vasil'ev presented a branch-and-price-and-cut algorithm to solve large-scale instances of the p-median problem in "Computational study of large-scale p-median problems". This involves a column-and-row generation strategy to solve a relaxed LP and cutting planes to strengthen the formulation. The authors reported computational results on large problems involving at least 900 nodes.

R. A. Whitaker detailed a drop algorithm in "A tight bound drop exchange algorithm for solving the p-median problem" that starts with all n nodes in the solution set and an objective value of 0. On each iteration, k nodes are removed from the solution set and (k − 1) nodes are brought back into the set, yielding a net loss of one node per iteration. On each iteration, the procedure attempts to minimize the amount that the objective value increases. The algorithm terminates when p vertices remain in the solution set. Computational results are presented comparing this method to a greedy interchange method.