The min-p robust optimization approach for facility location problem under uncertainty

Improper value of the parameter p in robust constraints will result in no feasible solutions while applying stochastic p-robustness optimization approach (p-SRO) to solving facility location problems under uncertainty. Aiming at finding the lowest critical p-value of parameter p and corresponding robust optimal solution, we developed a novel robust optimization approach named as min-p robust optimization approach (min-pRO) for P-median problem (PMP) and fixed cost P-median problem (FPMP). Combined with the nearest allocation strategy, the vertex substitution heuristic algorithm is improved and the influencing factors of the lowest critical p-value are analyzed. The effectiveness and performance of the proposed approach are verified by numerical examples. The results show that the fluctuation range of data is positively correlated with the lowest critical p-value with given number of new facilities. However, the number of new facilities has a different impact on lowest critical p-value with the given fluctuation range of data. As the number of new facilities increases, the lowest critical p-value for PMP and FPMP increases and decreases, respectively.

     

The facility location problem with Bernoulli demands

This paper presents the facility location problem with Bernoulli demands. In this capacitated discrete location stochastic problem the goal is to define an a priori solution for the locations of the facilities and for the allocation of customers to the operating facilities that minimizes the sum of the fixed costs of the open facilities plus the expected value of the recourse function. The problem is formulated as a two-stage stochastic program and two different recourse actions are considered. For each of them, a closed form is presented for the recourse function and a deterministic equivalent formulation is obtained for the case in which the probability of demand is the same for all customers. Numerical results from computational experiments are presented and analyzed.     

A note on the facility location problem with stochastic demands

In this research note that the single source capacitated facility location problem with general stochastic identically distributed demands is studied. The demands considered are independent and identically distributed random variables with arbitrary distribution. The unified a priori solution for the locations of facilities and for the allocation of customers to the operating facilities is found. This solution minimizes the objective function which is the sum of the fixed costs and the value of one of two different recourse functions. For each case the recourse function is given in closed form and a deterministic equivalent formulation of the model is presented. Some numerical examples are also given.     

Approximation algorithm for uniform bounded facility location problem

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0–1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+? for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756–765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424–436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.     

An improved approximation algorithm for uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the classical facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. The UFLWP problem has been effectively used to model the facility location problem with outliers. Three constant approximation algorithms have been obtained (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001; Jain et al. in J. ACM 50(6):795–824, 2003; Xu and Xu in Inf. Process. Lett. 94(3):119–123, 2005), and the best known performance ratio is 2. The only known hardness result is a 1.463-inapproximability result inherited from the uncapacitated facility location problem (Guha and Khuller in J. Algorithms 31(1):228–248, 1999). In this paper, We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm significantly reduces the gap between known performance ratio and the inapproximability result. Our algorithm first enhances the primal-dual method for the UFLWP problem (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001) so that outliers can be recognized more efficiently, and then applies a local search heuristic (Charikar and Guha in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pp. 378–388, 1999) to further reduce the cost for serving those non-rejected clients. Our algorithm is simple and can be easily implemented. The research of this work was supported in part by NSF through CAREER award CCF-0546509 and grant IIS-0713489. A preliminary version of this paper appeared in the Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON’05).     

An approximation algorithm for stochastic multi-level facility location problem with soft capacities

Journal of Combinatorial Optimization - Facility location problem is one of the most important problems in the combinatorial optimization. The multi-level facility location problem and the facility...     

An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties

Journal of Combinatorial Optimization - Facility location problem is a well established research area within Operations Research. Capacitated facility location problem is one of the most important...     

Line facility location in weighted regions

In this paper, we present approximation algorithms for solving the line facility location problem in weighted regions. The weighted region setup is a more realistic model for many facility location problems that arise in practical applications. Our algorithms exploit an interesting property of the problem, that could possibly be used for solving other problems in weighted regions.     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

Multiple facility location on a network with linear reliability order of edges

We study the problem of locating facilities on the nodes of a network to maximize the expected demand serviced. The edges of the input graph are subject to random failure due to a disruptive event. We consider a special type of failure correlation. The edge dependency model assumes that the failure of a more reliable edge implies the failure of all less reliable ones. Under this dependency model called Linear Reliability Order (LRO) we give two polynomial time exact algorithms. When two distinct LRO’s exist, we prove the total unimodularity of a linear programming formulation. In addition, we show that minimizing the sum of facility opening costs and expected cost of unserviced demand under two orderings reduces to a matching problem. We prove NP-hardness of the three orderings case and show that the problem with an arbitrary number of orderings generalizes the deterministic maximum coverage problem. When a demand point can be covered only if a facility exists within a distance limit, we show that the problem is NP-hard even for a single ordering.     

On multi-criteria chance-constrained capacitated single-source discrete facility location problems

This work aims at investigating multi-criteria modeling frameworks for discrete stochastic facility location problems with single sourcing. We assume that demand is stochastic and also that a service level is imposed. This situation is modeled using a set of probabilistic constraints. We also consider a minimum throughput at the facilities to justify opening them. We investigate two paradigms in terms of multi-criteria optimization: vectorial optimization and goal programming. Additionally, we discuss the joint use of objective functions that are relevant in the context of some humanitarian logistics problems. We apply the general modeling frameworks proposed to the so-called stochastic shelter site location problem. This is a problem emerging in the context of preventive disaster management. We test the models proposed using two real benchmark data sets. The results show that considering uncertainty and multiple objectives in the type of facility location problems investigated leads to solutions that may better support decision making.     

Strategyproof mechanism design for facility location games with weighted agents on a line

Approximation mechanism design without money was first studied in Procaccia and Tennenholtz (2009) by considering a facility location game. In general, a facility is being opened and the cost of an agent is measured by its distance to the facility. In order to achieve a good social cost, a mechanism selects the location of the facility based on the locations reported by agents. It motivates agents to strategically report their locations to get good outcomes for themselves. A mechanism is called strategyproof if no agents could manipulate to get a better outcome by telling lies regardless of any configuration of other agents. The main contribution in this paper is to explore the strategyproof mechanisms without money when agents are distinguishable. There are two main variations on the nature of agents. One is that agents prefer getting closer to the facility, while the other is that agents prefer being far away from the facility. We first consider the model that directly extends the model in Procaccia and Tennenholtz (2009). In particular, we consider the strategyproof mechanisms without money when agents are weighted. We show that the strategyproof mechanisms in the case of unweighted agents are still the best in the weighted cases. We establish tight lower and upper bounds for approximation ratios on the optimal social utility and the minimum utility when agents prefer to stay close to the facility. We then provide the lower and upper bounds on the optimal social utility and lower bound on the minimum distance per weight when agents prefer to stay far away from the facility. We also extend our study in a natural direction where two facilities must be built on a real line. Secondly, we propose an novel threshold based model to distinguish agents. In this model, we present a strategyproof mechanism that leads to optimal solutions in terms of social cost.     

Mobile facility location: combinatorial filtering via weighted occupancy

An instance of the mobile facility location problem consists of a complete directed graph \(G = (V, E)\) , in which each arc \((u, v) \in E\) is associated with a numerical attribute \(\mathcal M (u,v)\) , representing the cost of moving any object from \(u\) to \(v\) . An additional ingredient of the input is a collection of servers \(S = \{ s_1, \ldots , s_k \}\) and a set of clients \(C = \{ c_1, \ldots , c_\ell \}\) , which are located at nodes of the underlying graph. With this setting in mind, a movement scheme is a function \(\psi : S \rightarrow V\) that relocates each server \(s_i\) to a new position, \(\psi ( s_i )\) . We refer to \(\mathcal M ( s_i, \psi ( s_i ) )\) as the relocation cost of \(s_i\) , and to \(\min _{i \in [k]} \mathcal M (c_j, \psi ( s_i ) )\) , the cost of assigning client \(c_j\) to the nearest final server location, as the service cost of \(c_j\) . The objective is to compute a movement scheme that minimizes the sum of relocation and service costs. In this paper, we resolve an open question posed by Demaine et al. (SODA ’07) by characterizing the approximability of mobile facility location through LP-based methods. We also develop a more efficient algorithm, which is based on a combinatorial filtering approach. The latter technique is of independent interest, as it may be applicable in other settings as well. In this context, we introduce a weighted version of the occupancy problem, for which we establish interesting tail bounds, not before demonstrating that existing bounds cannot be extended.     

The flow refueling location problem with load flow control

Battery electric vehicles as well as renewable energy are two key factors that can contribute significantly to sustainable development within the transportation and the energy sector. However, the market introduction of these technologies results in new challenges, especially with regard to the interaction between both sectors. So far, neither location models for charging stations nor load flow models for the electrical grid consider these interactions sufficiently. Thus, an integration of planning problems from both sectors is needed in order to exploit potential synergies and to avoid negative impacts.In this paper, we present such an integrated planning approach to locate charging infrastructure for battery electric vehicles considering interactions with the electrical grid. Herein, we combine a charging station location model and a power flow model with integrated energy stores. We aim at determining a network configuration that satisfies the charging demand of battery electric vehicles, herein maximizing the benefits and minimizing the negative impacts resulting from the interactions of the two sectors. To demonstrate the benefit of our integrated planning approach, we apply it to an illustrative case and present results of a sensitivity analysis. We derive managerial insights regarding the interdependencies of the number of sited charging stations and the installed storage capacity based on renewable energy generation and charging demand.     

Approximation strategy-proof mechanisms for obnoxious facility location on a line

In the facility location game on a line, there are some agents who have fixed locations on the line where an obnoxious facility will be placed. The objective is to maximize the social welfare, e.g., the sum of distances from the facility to all agents. On collecting location information, agents may misreport the locations so as to stay far away from the obnoxious facility. In this paper, strategy-proof mechanisms are designed and the approximation ratio is used to measure the performances of the strategy-proof mechanisms. Two objective functions, maximizing the sum of squares of distances (maxSOS) and maximizing the sum of distances (maxSum), have been considered. For maxSOS, a randomized 5/3-approximated strategy-proof mechanism is proposed, and the lower bound of the approximation ratio is proved to be at least 1.042. For maxSum, the lower bound of the approximation ratio of the randomized strategy-proof mechanism is proved to be 1.077. Moreover, a general model is considered that each agent may have multiple locations on the line. For the objective functions maxSum and maxSOS, both deterministic and randomized strategy-proof mechanisms are investigated, and the deterministic mechanisms are shown to be best possible.     

An hierarchal location—allocation problem

We consider a 2-hierarchal location-allocation problem when p₁ health centers and p₂ hospitals are to be located among n potential locations so as to minimize the total weighted travel distance. We consider the possibility of the referral of θ (0 ≤ θ ≤ 1) proportion of patients from a health center to a hospital. For a graph with certain properties, we extend the notion of a median of a graph to an hierarchal median set. We show how the 2-hierarchal location-allocation problem may be solved as a 2-hierarchal vertex median set problem. We formulate the problem as a mathematical programming problem, suggest five heuristic procedures to solve the problem and report some computational experience. Although we consider the hierarchal location-allocation problem with reference to a health care delivery system, the results of this paper have wide application.     

A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.     

Multimode time-cost-robustness trade-off project scheduling problem under uncertainty

The time/cost trade-off problem is a well-known project scheduling problem that has been extensively studied. In recent years, many researchers have begun to focus on project scheduling problems under uncertainty to cope with uncertain factors, such as resource idleness, high inventory, and missing deadlines. To reduce the disturbance from uncertain factors, the aim of robust scheduling is to generate schedules with time buffers or resource buffers, which are capped by project makespan and project cost. This paper addresses a time-cost-robustness trade-off project scheduling problem with multiple activity execution modes under uncertainty. A multiobjective optimization model with three objectives (makespan minimization, cost minimization, and robustness maximization) is constructed and three propositions are proposed. An epsilon-constraint method-based genetic algorithm along with three improvement measures is designed to solve this NP-hard problem and to develop Pareto schedule sets, and a large-scale computational experiment on a randomly generated dataset is performed to validate the effectiveness of the proposed algorithm and the improvement measures. The final sensitivity analysis of three key parameters shows their distinctive influences on the three objectives, according to which several suggestions are given to project managers on the effective measures to improve the three objectives.