Upper bounds for objective functions of discrete competitive facility location problems

Under study is the problem of locating facilities when two competing companies successively open their facilities. Each client chooses an open facility according to his own preferences and return interests to the leader firm or to the follower firm. The problem is to locate the leader firm so as to realize the maximum profit (gain) subject to the responses of the follower company and the available preferences of clients. We give some formulations of the problems under consideration in the form of two-level integer linear programming problems and, equivalently, as pseudo-Boolean two-level programming problems. We suggest a method of constructing some upper bounds for the objective functions of the competitive facility location problems. Our algorithm consists in constructing an auxiliary pseudo-Boolean function, which we call an estimation function, and finding the minimum value of this function. For the special case of the competitive facility location problems on paths, we give polynomial-time algorithms for finding optimal solutions. Some results of computational experiments allow us to estimate the accuracy of calculating the upper bounds for the competitive location problems on paths.     

A discrete competitive facility location model with variable attractiveness

We consider the discrete version of the competitive facility location problem in which new facilities have to be located by a new market entrant firm to compete against already existing facilities that may belong to one or more competitors. The demand is assumed to be aggregated at certain points in the plane and the new facilities can be located at predetermined candidate sites. We employ Huff's gravity-based rule in modelling the behaviour of the customers where the probability that customers at a demand point patronize a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. The objective of the firm is to determine the locations of the new facilities and their attractiveness levels so as to maximize the profit, which is calculated as the revenue from the customers less the fixed cost of opening the facilities and variable cost of setting their attractiveness levels. We formulate a mixed-integer nonlinear programming model for this problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and another branch-and-bound method with nonlinear programming relaxation. Computational results obtained on a set of randomly generated instances show that the last method outperforms the others in terms of accuracy and efficiency and can provide an optimal solution in a reasonable amount of time.     

Heuristic algorithms for delivered price spatially competitive network facility location problems

We review previous formulations of models for locating a firm's production facilities while simultaneously determining production levels at those facilities so as to maximize the firm's profit. We enhance these formulations by adding explicit variables to represent the firm's shipping activities and discuss the implications of this revised approach. In these formulations, existing firms, as well as new entrants, are assumed to act in accordance with an appropriate model of spatial equilibrium. The firm locating new production facilities is assumed to be a large manufacturer entering an industry composed of a large number of small firms. Our previously reported proof of existence of a solution to the combined location-equilibrium problem is briefly reviewed. A heuristic algorithm based on sensitivity analysis methods which presume the existence of a solution and which locally approximate price changes as linear functions of production perturbations resulting from newly established facilities is presented. We provide several numerical tests to illustrate the contrasting locational solutions which this paper's revised delivered price formulation generates relative to those of previous formulations. An exact, although computationally burdensome, method is also presented and employed to check the reliability of the heuristic algorithm.     

A capacitated competitive facility location problem

We consider a mathematical model similar in a sense to competitive location problems. There are two competing parties that sequentially open their facilities aiming to “capture” customers and maximize profit. In our model, we assume that facilities’ capacities are bounded. The model is formulated as a bilevel integer mathematical program, and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as that of maximization of a pseudo-Boolean function with the number of arguments equal to the number of places available for facility opening. We propose an algorithm for calculating an upper bound for values that the function takes on subsets which are specified by partial (0, 1)-vectors.     

Modelling lost demand in competitive facility location

In this paper, we propose a simple new approach to model lost demand (also referred to as elastic demand) in competitive facility location. A ‘dummy’ competing facility that attracts the lost demand is added to the list of competing facilities. All competitive facility location models, regardless of their complexity or assumptions, can be modified to include lost demand and be solved by the same algorithms designed for standard models once the dummy facility is added to the data as an additional competitor.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Optimal location and design of a competitive facility

A single facility has to be located in competition with fixed existing facilities of similar type. Demand is supposed to be concentrated at a finite number of points, and consumers patronise the facility to which they are attracted most. Attraction is expressed by some function of the quality of the facility and its distance to demand. For existing facilities quality is fixed, while quality of the new facility may be freely chosen at known costs. The total demand captured by the new facility generates income. The question is to find that location and quality for the new facility which maximises the resulting profits.It is shown that this problem is well posed as soon as consumers are novelty oriented, i.e. attraction ties are resolved in favour of the new facility. Solution of the problem then may be reduced to a bicriterion maxcovering-minquantile problem for which solution methods are known. In the planar case with Euclidean distances and a variety of attraction functions this leads to a finite algorithm polynomial in the number of consumers, whereas, for more general instances, the search of a maximal profit solution is reduced to solving a series of small-scale nonlinear optimisation problems. Alternative tie-resolution rules are finally shown to result in problems in which optimal solutions might not exist.Mathematics Subject Classification (2000):90B85, 90C30, 90C29, 91B42Partially supported by Grant PB96-1416-C02-02 of the D.G.E.S. and Grant BFM2002-04525-C02-02 of Ministerio de Ciencia y Tecnología, Spain     

A flexible model and efficient solution strategies for discrete location problems

Flexible discrete location problems are a generalization of most classical discrete locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer, which depends on the position of that cost relative to the costs of fulfilling the demand of other customers.In this paper a covering type of model for the discrete ordered median problem is presented. For the solution of this model two sets of valid inequalities, which reduces the number of binary variables tremendously, and several variable fixing strategies are identified. Based on these concepts a specialized branch & cut procedure is proposed and extensive computational results are reported.     

Approximate algorithms for the competitive facility location problem

We consider the competitive facility location problem in which two competing sides (the Leader and the Follower) open in succession their facilities, and each consumer chooses one of the open facilities basing on its own preferences. The problem amounts to choosing the Leader’s facility locations so that to obtain maximal profit taking into account the subsequent facility location by the Follower who also aims to obtain maximal profit. We state the problem as a two-level integer programming problem. A method is proposed for calculating an upper bound for the maximal profit of the Leader. The corresponding algorithm amounts to constructing the classical maximum facility location problem and finding an optimal solution to it. Simultaneously with calculating an upper bound we construct an initial approximate solution to the competitive facility location problem. We propose some local search algorithms for improving the initial approximate solutions. We include the results of some simulations with the proposed algorithms, which enable us to estimate the precision of the resulting approximate solutions and give a comparative estimate for the quality of the algorithms under consideration for constructing the approximate solutions to the problem.     

一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

Existence theory for spatially competitive network facility location models

Models for locating a firm's production facilities while simultaneously determining production levels at these facilities and shipping patterns so as to maximize the firm's profits are presented. In these models, existing firms, are assumed to act in accordance with an appropriate model of spatial equilibrium. A proof of existence of a solution to the combined location-equilibrium problem is provided.     

Recent insights in Huff-like competitive facility location and design

Recently, several articles appeared on the location–design problem that firms face when entering a competing market. All use a Huff-like attraction model. We discuss the formulation of the base model, the different settings studied in the papers and summarise their findings.     

Capacitated facility location/network design problems

We introduce a combined facility location/network design problem in which facilities have constraining capacities on the amount of demand they can serve. This model has a number of applications in regional planning, distribution, telecommunications, energy management, and other areas. Our model includes the classical capacitated facility location problem (CFLP) on a network as a special case. We present a mixed integer programming formulation of the problem, and several classes of valid inequalities are derived to strengthen its LP relaxation. Computational experience with problems with up to 40 nodes and 160 candidate links is reported, and a sensitivity analysis provides insight into the behavior of the model in response to changes in key problem parameters.     

Static competitive facility location: An overview of optimisation approaches

We give an overview of the research, models and literature about optimisation approaches to the problem of optimally locating one or more new facilities in an environment where competing facilities are already established.     

A two-player competitive discrete location model with simultaneous decisions

In this paper we will describe and study a competitive discrete location problem in which two decision-makers (players) will have to decide where to locate their own facilities, and customers will be assigned to the closest open facilities. We will consider the situation in which the players must decide simultaneously, unsure about the decisions of one another, and we will present the problem in a franchising environment. Most problems described in the literature consider sequential rather than simultaneous decisions. In a competitive environment, most problems consider that there is a set of known and already located facilities, and new facilities will have to be located, competing with the existing ones. In the presence of more than one decision-maker, most problems found in the literature belong to the class of Stackelberg location problems, where one decision-maker, the leader, locates first and then the other decision-maker, the follower, locates second, knowing the decisions made by the first. These types of problems are sequential and differ significantly from the problem tackled in this paper, where we explicitly consider simultaneous, non-cooperative discrete location decisions. We describe the problem and its context, propose some mathematical formulations and present an algorithmic approach that was developed to find Nash equilibria. Some computational tests were performed that allowed us to better understand some of the features of the problem and the associated Nash equilibria. Among other results, we conclude that worsening the situation of a player tends to benefit the other player, and that the inefficiency of Nash equilibria tends to increase with the level of competition.     

The discrete facility location problem with balanced allocation of customers

We consider a discrete facility location problem where the difference between the maximum and minimum number of customers allocated to every plant has to be balanced. Two different Integer Programming formulations are built, and several families of valid inequalities for these formulations are developed. Preprocessing techniques which allow to reduce the size of the largest formulation, based on the upper bound obtained by means of an ad hoc heuristic solution, are also incorporated. Since the number of available valid inequalities for this formulation is exponential, a branch-and-cut algorithm is designed where the most violated inequalities are separated at every node of the branching tree. Both formulations, with and without the improvements, are tested in a computational framework in order to discriminate the most promising solution methods. Difficult instances with up to 50 potential plants and 100 customers, and largest easy instances, can be solved in one CPU hour.     

Closest assignment constraints in discrete location problems

The objective of this paper is to identify the most promising sets of closest assignment constraints in the literature of Discrete Location Theory, helping the authors in the field to model their problems when clients must be assigned to the closest plant inside an Integer Programming formulation. In particular, constraints leading to weak Linear Programming relaxations should be avoided if no other good property supports their use. We also propose a new set of constraints with good theoretical properties.     

Multiple criteria facility location problems: A survey

This paper provides a review on recent efforts and development in multi-criteria location problems in three categories including bi-objective, multi-objective and multi-attribute problems and their solution methods. Also, it provides an overview on various criteria used. While there are a few chapters or sections in different location books related to this topic, we have not seen any comprehensive review papers or book chapter that can cover it. We believe this paper can be used as a complementary and updated version.     

Single facility location problems with unbounded unit balls

In this paper we consider a new class of continuous location problems where the distances are measured by gauges of closed (not necessarily bounded) convex sets. These distance functions do not satisfy the definiteness property and therefore they can be used to model those situations where there exist zero-distance regions. We prove a geometrical characterization of these measures of distance as the length of shortest paths between points using only a subset of directions of their unit balls. We also characterize the complete set of optimal solutions for this class of continuous single facility location problems and we give resolution methods to solve them. Our analysis allows to consider new models of location problems and generalizes previously known results.     

Improved approximation algorithms for capacitated facility location problems

In a surprising result, Korupolu, Plaxton, and Rajaraman [13] showed that a simple local search heuristic for the capacitated facility location problem (CFLP) in which the service costs obey the triangle inequality produces a solution in polynomial time which is within a factor of 8+ of the value of an optimal solution. By simplifying their analysis, we are able to show that the same heuristic produces a solution which is within a factor of 6(1+) of the value of an optimal solution. Our simplified analysis uses the supermodularity of the cost function of the problem and the integrality of the transshipment polyhedron.Additionally, we consider the variant of the CFLP in which one may open multiple copies of any facility. Using ideas from the analysis of the local search heuristic, we show how to turn any -approximation algorithm for this variant into a polynomial-time algorithm which, at an additional cost of twice the optimum of the standard CFLP, opens at most one additional copy of any facility. This allows us to transform a recent 2-approximation algorithm of Mahdian, Ye, and Zhang [17] that opens many additional copies of facilities into a polynomial-time algorithm which only opens one additional copy and has cost no more than four times the value of the standard CFLP.This research was performed while the author was a postdoctoral fellow at the IBM T.J. Watson Research Center.This research was performed while the author was a Research Staff Member at the IBM T.J. Watson Research Center.A preliminary version of this paper appeared in the Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization [9].