An effective heuristic for large-scale capacitated facility location problems

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facilities with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. The heuristic is based on a Lagrangean relaxation which is used to select a subset of “promising” variables forming the core problem and on a Branch-and-Cut algorithm that solves the core problem. Computational results on very large scale instances (up to 4 million variables) are reported.     

LP-based approximation algorithms for capacitated facility location

In the capacitated facility location problem with hard capacities, we are given a set of facilities, ${\mathcal{F}}$ , and a set of clients ${\mathcal{D}}$ in a common metric space. Each facility i has a facility opening cost f _i and capacity u _i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set ${\mathcal{F}}$ and assign each client to an open facility so that at most u _i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by the distance c _ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs. The only known approximation algorithms that deliver solutions within a constant factor of optimal for this NP-hard problem are based on local search techniques. It is an open problem to devise an approximation algorithm for this problem based on a linear programming lower bound (or indeed, to prove a constant integrality gap for any LP relaxation). We make progress on this question by giving a 5-approximation algorithm for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. One notable aspect of our algorithm is that it relies on partitioning the input into a collection of single-demand capacitated facility location problems, approximately solving them, and then combining these solutions in a natural way.     

LP-based approximation for uniform capacitated facility location problem

In this paper, we study uniform hard capacitated facility location problem. The standard LP for the problem is known to have an unbounded integrality gap. We present constant factor approximation by rounding a solution to the standard LP with a slight $(1+ϵ)$ violation in the capacities.Our result shows that the standard LP is not too bad.Our algorithm is simple and more efficient as compared to the strengthened LP-based true approximation that uses the inefficient ellipsoid method with a separation oracle. True approximations are also known for the problem using local search techniques that suffer from the problem of convergence. Moreover, solutions based on standard LP are easier to integrate with other LP-based algorithms.The result is also extended to give the first approximation for uniform hard capacitated $k$-facility location problem violating the capacities by a factor of $(1+ϵ)$ and breaking the barrier of 2 in capacity violation. The result violates the cardinality by a factor of $\frac{2}{1+ϵ}$.     

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].     

A tabu search heuristic procedure for the capacitated facility location problem

A tabu search heuristic procedure is developed, implemented and computationally tested for the capacitated facility location problem. The procedure uses different memory structures. Visited solutions are stored in a primogenitary linked quad tree. For each facility, the recent move at which the facility changed its status and the frequency it has been open are also stored. These memory structures are used to guide the main search process as well as the diversification and intensification processes. Lower bounds on the decreases of total cost are used to measure the attractiveness of the moves and to select moves in the search process. A specialized network algorithm is developed to exploit the problem structure in solving transportation problems. Criterion altering, solution reconciling and path relinking are used to perform intensification functions. The performance of the procedure is tested through computational experiments using test problems from the literature and new test problems randomly generated. It found optimal solutions for almost all test problems from the literature. As compared to the heuristic method of Lagrangean relaxation with improved subgradient scheme, the tabu search heuristic procedure found much better solutions using much less CPU time.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

An exact algorithm for the capacitated facility location problems with single sourcing

Facility location problems are often encountered in many areas such as distribution, transportation and telecommunication. We describe a new solution approach for the capacitated facility location problem in which each customer is served by a single facility. An important class of heuristic solution methods for these problems are Lagrangian heuristics which have been shown to produce high quality solutions and at the same time be quite robust. A primal heuristic, based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied, is incorporated into the Lagrangian heuristic. Finally, a branch-and-bound method, based on the Lagrangian heuristic is developed, and compared computationally to the commercial code CPLEX. The computational results indicate that the proposed method is very efficient.     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.     

Solving capacitated facility location problems by Fenchel cutting planes

In this paper, we apply the Fenchel cutting planes methodology to Capacitated Facility Location problems. We select a suitable knapsack structure from which depth cuts can be obtained. Moreover, we simultaneously obtain a primal heuristic solution. The lower and upper bounds achieved by our procedure are compared with those provided by Lagrangean relaxation of the demand constraints. As the computational results show the Fenchel cutting planes methodology outperforms the Lagrangean one, both in the obtaining of the bounds and in the effectiveness of the branch and bound algorithm using each relaxation as the initial formulation.     

A cross entropy-based metaheuristic algorithm for large-scale capacitated facility location problems

In this paper, we present a metaheuristic-based algorithm for the capacitated facility location problem. The proposed scheme is made up by three phases: (i) solution construction phase, in which a cross entropy-based scheme is used to ‘intelligently’ guess which facilities should be opened; (ii) local search phase, aimed at exploring the neighbourhood of ‘elite’ solutions of the previous phase; and (iii) learning phase, aimed at fine-tuning the stochastic parameters of the algorithm. The algorithm has been thoroughly tested on large-scale random generated instances as well as on benchmark problems and computational results show the effectiveness and robustness of the algorithm.     

Solving the robust two-stage capacitated facility location problem with uncertain transportation costs

In this study, we start from a multi-source variant of the two-stage capacitated facility location problem (TSCFLP) and propose a robust optimization model of the problem that involves the uncertainty of transportation costs. Since large dimensions of the robust TSCFLP could not be solved to optimality, we design a memetic algorithm (MA), which represents a combination of an evolutionary algorithm (EA) and a modified simulated annealing heuristic (SA) that uses a short-term memory of undesirable moves from previous iterations. A set of computational experiments is conducted to examine the impact of different protection levels on the deviation of the objective function value. We also investigate the impact of variations of transportation costs that may occur on both transhipment stages on the total cost for a fixed protection level. The obtained results may help in identifying a sustainable and efficient strategy for designing a two stage capacitated transportation network with uncertain transportation costs, and may be applicable in the design and management of similar transportation networks.     

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs

We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig–Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.     

Easy capacitated facility location problems,with connections to lot-sizing

In this note, we consider the capacitated facility location problem when the transportation costs of the instance satisfy the Monge property. We show that a straightforward dynamic program finds the optimal solution when the demands are polynomially bounded. When demands are not polynomially bounded, we give a fully polynomial-time approximation scheme by adapting an algorithm and analysis of Van Hoesel and Wagelmans (2001).     

An algorithm for solving large capacitated warehouse location problems

In this paper we present a lower bound for the capacitated warehouse location problem based upon lagrangean relaxation of a mixed-integer formulation of the problem. Feasible solution exclusion constraints are used together with problem reduction tests derived from both the original problem and the lagrangean relaxation.By incorporating the lower bound and the reduction tests into a tree search procedure we are able to solve problems involving up to 500 potential warehouse locations and 1000 customers.     

The ordered capacitated facility location problem

In this paper, we analyze flexible models for capacitated discrete location problems with setup costs. We introduce a major extension with regards to standard models which consists of distinguishing three different points of view of a location problem in a logistics system. We develop mathematical programming formulations for these models using discrete ordered objective functions with some new features. We report on the computational behavior of these formulations tested on a randomly generated battery of instances.     

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.     

Kernel search for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is among the most studied problems in the OR literature. Each customer demand has to be supplied by one or more facilities. Each facility cannot supply more than a given amount of product. The goal is to minimize the total cost to open the facilities and to serve all the customers. The problem is $\mathcal{NP}$ -hard. The Kernel Search is a heuristic framework based on the idea of identifying subsets of variables and in solving a sequence of MILP problems, each problem restricted to one of the identified subsets of variables. In this paper we enhance the Kernel Search and apply it to the solution of the CFLP. The heuristic is tested on a very large set of benchmark instances and the computational results confirm the effectiveness of the Kernel Search framework. The optimal solution has been found for all the instances whose optimal solution is known. Most of the best known solutions have been improved for those instances whose optimal solution is still unknown.     

Optimal cost sharing for capacitated facility location games

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.     

An improved per-scenario bound for the two-stage stochastic facility location problem

We study the two-stage stochastic facility location problem(2-SFLP)by proposing an LP(location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem,improving the previously best per-scenario bound of 2.4957.     

Accelerating Benders' decomposition for the capacitated facility location problem

Discrete facility location problems are attractive candidates for decomposition procedures since two types of decisions have to be performed: on the one hand the yes/no-decision where to locate the facilities, on the other hand the decision how to allocate the demand to the selected facilities. Nevertheless, Benders' decomposition seems to have a rather slow convergence behaviour when applied for solving location problems. In the following, a procedure will be presented for strengthening the Benders' cuts for the capacitated facility location problem. Computational results show the efficiency of the modified Benders' decomposition algorithm. Furthermore, the paretooptimality of the strengthened Benders' cuts in the sense of [Magnanti and Wong 1990] is shown under a weak assumption.This paper was written when the author was at the Institute for Operations Research, University of St. Gallen, Switzerland, and partly supported by Schweizerischer Nationalfond zur Förderung der wissenschaftlichen Forschung (Grant 12-30140.90).