A graph theoretical bound for the p-median problem

The p-median problem is a minisium network location problem that seeks to find the optimal location of p centres in a network. In the present paper a graph-theoretical bound is developed for the problem. This bound is based on shortest spanning trees and arborescences and other graphical properties of the problem. It is shown that the graph-theoretical bound dominates a bound based on shortest distances.     

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.     

A mixed integer programming formulation for the 1-maximin problem

In this paper, I present a mixed integer programming (MIP) formulation for the 1-maximin problem with rectilinear distance. The problem mainly appears in facility location while trying to locate an undesirable facility. The rectilinear distance is quite commonly used in the location literature. Our numerical experiments show that one can solve reasonably large location problems using a standard MIP solver. We also provide a linear programming formulation that helps find an upper bound on the objective function value of the 1-maximin problem with any norm when extreme points of the feasible region are known. We discuss various extension alternatives for the MIP formulation.     

Extensions to a Lagrangean relaxation approach for the capacitated warehouse location problem

In this paper we present a lower bound for the capacitated warehouse location problem based upon the Lagrangean relaxation of a mixed-integer formulation of the problem, where we use subgradient optimisation in an attempt to maximise this lower bound. Problem reduction tests based upon this lower bound and the original problem are given. Incorporating this bound and the reduction tests into a tree search procedure enables us to solve problems involving up to 50 warehouses and 150 customers.     

An Improved Algorithm for the Multi-commodity Location Problem

Distribution systems designs commonly require the optimal location decisions of regional ware-houses or distribution centers which function as intermediate facilities between plants and customers. This paper deals with such a location problem in which the facilities can handle one of several commodities. We term this problem the multi-commodity facility location problem. A branch and bound algorithm is proposed for solving this problem. Improved bounds are developed for increasing the efficiency of the algorithm. Computational results are provided.     

A Lagrangian heuristic for concave cost facility location problems: the plant location and technology acquisition problem

We propose a Lagrangian heuristic for facility location problems with concave cost functions and apply it to solve the plant location and technology acquisition problem. The problem is decomposed into a mixed integer subproblem and a set of trivial single-variable concave minimization subproblems. We are able to give a closed-form expression for the optimal Lagrangian multipliers such that the Lagrangian bound is obtained in a single iteration. Since the solution of the first subproblem is feasible to the original problem, a feasible solution and an upper bound are readily available. The Lagrangian heuristic can be embedded in a branch-and-bound scheme to close the optimality gap. Computational results show that the approach is capable of reaching high quality solutions efficiently. The proposed approach can be tailored to solve many concave-cost facility location problems.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

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.     

A Note on Warszawski's Multi-Commodity Location Problem

This note shows two easily incorporated improvements in computing the lower bounds for Warszawski's branch and bound algorithm for the multi-commodity location problem. The lower bounds become relatively stronger, thereby making the branch and bound algorithm more efficient.     

A splitter location–allocation problem in designing fiber optic access networks

This paper deals with a physical access network design problem of fiber-to-the-home passive optical network (FTTH-PON). The design of FTTH-PON access network seeks the cost effective location of optical splitters that provide optical connectivity from central office to subscribers in a given service area. We formulate the problem as a multi-level capacitated facility location problem on a tree topology with nonlinear link cost. Dealing with the nonlinear link cost, we propose an objective function relaxation approach to obtain tight upper and lower bounds. We develop valid inequalities that enhance the lower bound and propose a local search heuristic procedure that improves the upper bound. Valid inequalities force integrality condition on the number of splitters placed at nodes. Local search heuristic improves the initial greedy solution by placing splitters on the sub-root nodes of a given tree network. Computational results demonstrate the effectiveness of the proposed solution procedures.     

The Multi-Story Space Assignment Problem

The Multi-Story Space Assignment Problem (MSAP) is an innovative formulation of the multi-story facility assignment problem that allows one to model the location of departments of unequal size within multi-story facilities as a Generalized Quadratic 3-dimensional Assignment Problem (GQ3AP). Not only can the MSAP generate the design of the location of the departments in the facility, the MSAP also includes the evacuation planning for the facility. The formulation, background mathematical development, and computational experience with a branch and bound algorithm for the MSAP are also presented.     

Solving the Simple Plant Location Problem using a Data Correcting Approach

The Data Correcting Algorithm is a branch and bound type algorithm in which the data of a given problem instance is `corrected' at each branching in such a way that the new instance will be as close as possible to a polynomially solvable instance and the result satisfies an acceptable accuracy (the difference between optimal and current solution). In this paper the data correcting algorithm is applied to determining exact and approximate optimal solutions to the simple plant location problem. Implementations of the algorithm are based on a pseudo-Boolean representation of the goal function of this problem, and a new reduction rule. We study the efficiency of the data correcting approach using two different bounds, the Khachaturov-Minoux bound and the Erlenkotter bound. We present computational results on several benchmark instances, which confirm the efficiency of the data-correcting approach.     

An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

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

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

Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands

In this paper, the capacitated location-routing problem with fuzzy demands (CLRP-FD) is considered. In CLRP-FD, facility location problem (FLP) and vehicle routing problem (VRP) are observed simultaneously. Indeed, the vehicles and the depots have a predefined capacity to serve the customers that have fuzzy demands. To model this problem, a fuzzy chance constrained programming model of that is designed based upon the fuzzy credibility theory. To solve this problem, a greedy clustering method (GCM) including the stochastic simulation is proposed. To obtain the best value of the dispatcher preference index of the model and to analyze its influence on the final solution, numerical experiments are carried out. Finally, to show the performance of the greedy clustering method, associated results are compared with the lower bound of the solutions.     

Urban rapid transit network capacity expansion

This paper examines a multi-period capacity expansion problem for rapid transit network design. The capacity expansion is realized through the location of train alignments and stations in an urban traffic context by selecting the time periods. The model maximizes the public transportation demand using a limited budget and designing lines for each period. The location problem incorporates the user decisions about mode and route. The network capacity expansion is a long-term planning problem because the network is built over several periods, in which the data (demand, resource price, etc.) are changing like the real problem changes. This complex problem cannot be solved by branch and bound, and for this reason, a heuristic approach has been defined in order to solve it. Both methods have been experimented in test networks.     

Rectilinear Location Revisited

In this note we study the multidimensional maximin rectilinear location problem. A general framework is given, partial optimal solutions introduced—together with an algorithm and its properties—and an upper bound analysis is conducted.     

Well-posedness for the massive nonlinear wave equation on asymptotically AdS spacetimes

In this paper, we prove some well-posedness theorems for the nonlinear massive wave equation (with the mass satisfying the Breitenlohner-Freedman bound) on asymptotically anti-de Sitter spaces. The solution is constructed by contraction mapping method and also as a limit of solutions to an initial boundary value problem with boundary at a finite location in spacetime by finally pushing the boundary out to infinity. The solution obtained is unique within the energy class.     

An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem

This contribution is focused on an acceleration of branch and bound algorithms for the uncapacitated facility location problem. Our approach is based on the well-known Erlenkotters’ procedures and Körkels’ multi-ascent and multi-adjustment algorithms, which have proved to be the efficient tools for solving the large-sized instances of the uncapacitated facility location problem. These two original approaches were examined and a thorough analysis of their performance revealed how each particular procedure contributes to the computational time of the whole algorithms. These analyses helped us to focus our effort on the most frequent procedures. The unique contribution of this paper is a new dual ascent procedure. This procedure leads to considerable acceleration of the lower bound computation process and reduces the resulting computational time. To demonstrate more efficient performance of amended algorithms we present the results of extensive numerical experiments.     

Branch and Bound Algorithm for the <Emphasis Type="Italic">p</Emphasis>-Median Transportation Problem

The p-median transportation problem is to determine an optimal solution to a transportation problem having an additional constraint restricting the number of active supply points. The model is discussed as an example of a public sector location/allocation problem. A branch and bound procedure is proposed to solve the problem. Lagrangian relaxation is used to provide lower bounds. Computational results are given.