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 new Lagrangean approach to the pooling problem

We present a new Lagrangean approach for the pooling problem. The relaxation targets all nonlinear constraints, and results in a Lagrangean subproblem with a nonlinear objective function and linear constraints, that is reformulated as a linear mixed integer program. Besides being used to generate lower bounds, the subproblem solutions are exploited within Lagrangean heuristics to find feasible solutions. Valid cuts, derived from bilinear terms, are added to the subproblem to strengthen the Lagrangean bound and improve the quality of feasible solutions. The procedure is tested on a benchmark set of fifteen problems from the literature. The proposed bounds are found to outperform or equal earlier bounds from the literature on 14 out of 15 tested problems. Similarly, the Lagrangean heuristics outperform the VNS and MALT heuristics on 4 instances. Furthermore, the Lagrangean lower bound is equal to the global optimum for nine problems, and on average is 2.1% from the optimum. The Lagrangean heuristics, on the other hand, find the global solution for ten problems and on average are 0.043% from the optimum.     

A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single-Source Constraints

Facility location models are applicable to problems in many diverse areas, such as distribution systems and communication networks. In capacitated facility location problems, a number of facilities with given capacities must be chosen from among a set of possible facility locations and then customers assigned to them. We describe a Lagrangian relaxation heuristic algorithm for capacitated problems in which each customer is served by a single facility. By relaxing the capacity constraints, the uncapacitated facility location problem is obtained as a subproblem and solved by the well-known dual ascent algorithm. The Lagrangian relaxations are complemented by an add heuristic, which is used to obtain an initial feasible solution. Further, a final adjustment heuristic is used to attempt to improve the best solution generated by the relaxations. Computational results are reported on examples generated from the Kuehn and Hamburger test problems.     

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.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0-1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.     

A heuristic lagrangean algorithm for the capacitated plant location problem

Lagrangean techniques have been widely applied to the uncapacitated plant location problem, and in some cases they have proven to be successfull even when capacitated problems with additional constraints are taken into account. In our paper we study the application of these techniques to the capacitated plant location problem when the model considered is a pure integer one. Several lagrangean decompositions are considered and for some of them heuristic algorithms have been designed to solve the resulting lagrangean subproblems, the heuristics consisting of a two phase procedure. The first (location phase) defines a set of multipliers from the analysis of the dual LP relaxation, and makes a choice of the plants considering the resulting subproblems as a particular case of the general assignment problems. Several heuristics have been studied for this second phase, based either on a decomposition of knapsack type subproblems through a definition of a set of penalties, or of looking into the duality gap and trying to reduce it. Computational experience is reported.     

An Algorithm for the Design of Multitype Concentrator Networks

In recent years we have witnessed remarkable progress in the development of the topological design of computer communication networks. One of the important aspects of the topological design of computer communication networks is the concentrator location problem. This problem is a complex combinatorial problem that belongs to the difficult class of NP-complete problems where the computation of an optimal solution is still a challenging task. This paper extends the standard capacitated concentrator location problem to a generalization of multitype capacitated concentrator location problems and presents an efficient algorithm based on cross decomposition. This algorithm incorporates the Benders decomposition and Lagrangean relaxation methods into a single framework and exploits the resulting primal and dual structure simultaneously. Computational results are quite satisfactory and encouraging and show this algorithm to be both efficient and effective. The use of cross decomposition as a heuristic algorithm is also discussed.     

Material allocation in MRP with tardiness penalties

In this paper, we address some flaws in the material allocation function of Materials Requirements Planning (MRP). The problem formulation differs from standard MRP logic in certain important ways: start and finish times for orders are forced to be realistic and material allocations are made to minimize the total tardiness penalty associated with late completion. We show that the resulting MRP material allocation problem is NP-hard in the strong sense. A lower bound and a heuristic are developed from a mixed integer linear formulation and its Lagrangean relaxation. The lower bound and the heuristics are closer to the optimum in cases where there is either abundant material or considerable competition for material; in intermediate cases, small perturbations in material allocation can have a significant effect. A group of heuristics based on the MRP approach and its modifications is examined; they are optimal under certain conditions. An improvement method that preserves priorities inherent in any given starting solution is also presented. The Lagrangean heuristic performs better than the MRP based heuristics for a set of 3900 small problems, yielding solutions that are about 5% to 10% over the optimal. The best MRP based heuristic does about as well as the Lagrangean heuristic on a set of 120 larger problems, and is 25% to 40% better than the standard MRP approach, on the data sets tested.     

Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.     

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

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

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

On the Extent to Which Certain Fixed-Charge Depot Location Problems can be Solved by LP

This paper considers a class of feasible set fixed-charge depot location problems which have been formulated as mixed-integer programmes. Computational results are reported to show that linear programming often produces integer solutions to uncapacitated problems as required. It is suggested that this represents a practical solution approach. Computational evidence suggests this convenient property does not extend to capacitated problems.Discussion of reducing infinite set problems to such feasible set problems is included.     

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.     

On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times

We address the multi-item, capacitated lot-sizing problem (CLSP) encountered in environments where demand is dynamic and to be met on time. Items compete for a limited capacity resource, which requires a setup for each lot of items to be produced causing unproductive time but no direct costs. The problem belongs to a class of problems that are difficult to solve. Even the feasibility problem becomes combinatorial when setup times are considered. This difficulty in reaching optimality and the practical relevance of CLSP make it important to design and analyse heuristics to find good solutions that can be implemented in practice. We consider certain mixed integer programming formulations of the problem and develop heuristics including a curtailed branch and bound, for rounding the setup variables in the LP solution of the tighter formulations. We report our computational results for a class of instances taken from literature.     

Lagrangian heuristics for the two-echelon,single-source,capacitated facility location problem

Facility location problems form an important class of integer programming problems, with application in the distribution and transportation industries. In this paper we are concerned with a particular type of facility location problem in which there exist two echelons of facilities. Each facility in the second echelon has limited capacity and can be supplied by only one facility (or depot) in the first echelon. Each customer is serviced by only one facility in the second echelon. The number and location of facilities in both echelons together with the allocation of customers to the second-echelon facilities are to be determined simultaneously. We propose a mathematical model for this problem and consider six heuristics based on Lagrangian relaxation for its solution. To solve the dual problem we make use of a subgradient optimization procedure. We present numerical results for a large suite of test problems. These indicate that the lower-bounds obtained from some relaxations have a duality gap which frequently is one third of the one obtained from traditional linear programming relaxation. Furthermore, the overall solution time for the heuristics are less than the time to solve the LP relaxation.     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem

The multi-stage capacitated lot sizing and loading problem (MCLSLP) deals with the issue of determining the lot sizes of product items in serially-arranged manufacturing stages and loading them on parallel facilities in each stage to satisfy dynamic demand over a given planning horizon. It is assumed that regular time capacity decisions have already been made in the tactical level and allocated to the stages, but it is still an important decision problem whether to augment regular time capacity by overtime capacity. Each item may be processed on a technologically feasible subset of existing facilities with different process and setup times on each facility. Since the solution of the MCLSLP requires the design of a powerful algorithm, simulated annealing (SA) and genetic algorithms (GA) are integrated to enhance their individual performances. Furthermore, these global optimisation methods are incorporated into a Lagrangean relaxation scheme, hence creating a hybrid solution methodology. Numerical results obtained using these methods confirm the mutual benefits of integrating different solution techniques.     

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

We present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). We show that the ACCPM based Benders cuts are both pareto-optimal and valid for any node of the branch-and-bound tree. The valid cuts are added to a pool of cuts that is used to warm-start the solution of the nodes after branching. The algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem. For the capacitated facility location problem, the proposed approach was on average 2.5 times faster than Benders-branch-and-cut and 11 times faster than classical Benders decomposition. For the multicommodity capacitated fixed charge network design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the majority of the tested instances.     

An Improved Algorithm for the Capacitated Facility Location Problem

In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.