Determining an Optimal Penetration Among Weighted Regions in Two and Three Dimensions

We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3-D spaces. This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering. Our algorithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penetration problem can be reduced to solving O(n ^2(d–1)) instances of certain special types of non-linear optimization problems, where n is the total number of vertices of the regions. We also give implementation results of our 2-D algorithms.     

Computing Optimal Beams in Two and Three Dimensions

The problem of computing an optimal beam among weighted regions (called the optimal beam problem) arises in several applied areas such as radiation therapy, stereotactic brain surgery, medical surgery, geological exploration, manufacturing, and environmental engineering. In this paper, we present computational geometry techniques that enable us to develop efficient algorithms for solving various optimal beam problems among weighted regions in two and three dimensional spaces. In particular, we consider two types of problems: the covering problems (seeking an optimal beam to contain a specified target region), and the piercing problems (seeking an optimal beam of a fixed shape to pierce the target region). We investigate several versions of these problems, with a variety of beam shapes and target region shapes in 2-D and 3-D. Our algorithms are based on interesting combinations of computational geometry techniques and optimization methods, and transform the optimal beam problems to solving a collection of instances of certain special non-linear optimization problems. Our approach makes use of interesting geometric observations, such as utilizing some new features of Minkowski sums.     

Median problems with positive and negative weights on cycles and cacti

This paper deals with facility location problems on graphs with positive and negative vertex weights. We consider two different objective functions: In the first one (MWD) vertices with positive weight are assigned to the closest facility, whereas vertices with negative weight are assigned to the farthest facility. In the second one (WMD) all the vertices are assigned to the nearest facility. For the MWD model it is shown that there exists a finite set of points in the graph which contains the locations of facilities in an optimal solution. Furthermore, algorithms for both models for the 2-median problem on a cycle are developed. The algorithm for the MWD model runs in linear time, whereas the algorithm for the WMD model has a time complexity of  O(n²)\mathcal{O}(n^{2}) .     

基于持续运营机会约束的竞争设施点选址研究——一种有效的实数编码遗传求解算法

竞争设施点选址是空间经济、区域发展、组合优化和系统工程的重要课题之一。本文以市场份额最大化为目标,研究了基于持续运营机会约束的竞争设施点选址问题,并给出了一种有效的实数编码遗传求解算法。在求解模型方面,首先假定运营成本是竞争设施点规模大小的函数,并对设施点持续运营概率进行机会约束,借鉴引力模型建立竞争设施点选址-设计问题的非线性混合整数规划模型。其次,考虑到选址变量和规模变量的数值类型,以及编码变换问题,设计了一种实数编码遗传求解算法。通过数值实验表明,对不同规模问题的实际计算结果,该算法可以在较短时间内获得最优解,可行解和精确解之间误差小于0.5%,相关比较分析也讨论了该算法的优越性和实用性,为竞争设施点选址问题的研究提供了不同的视角和实用求解算法。     

Approximating soft-capacitated facility location problem with uncertainty

In this paper we devise the stochastic and robust approaches to study the soft-capacitated facility location problem with uncertainty. We first present a new stochastic soft-capacitated model called The 2-Stage Soft Capacitated Facility Location Problem and solve it via an approximation algorithm by reducing it to linear-cost version of 2-stage facility location problem and dynamic facility location problem. We then present a novel robust model of soft-capacitated facility location, The Robust Soft Capacitated Facility Location Problem. To solve it, we improve the approximation algorithm proposed by Byrka et al. (LP-rounding algorithms for facility-location problems. CoRR, 2010a) for RFTFL and then treat it similarly as in the stochastic case. The improvement results in an approximation factor of \(\alpha + 4\) for the robust fault-tolerant facility location problem, which is best so far.     

基于混合蚁群算法的生产系统设施规划问题研究

设施规划问题主要研究生产设备的布局规划,从而减小厂区内的物料搬运成本。一个有效的设施规划有利于生产过程中整体运作效率的提高。随着市场竞争的日趋激烈,市场环境处于不断的变化之中,制造企业需不断对设施布局进行重新规划来适应不断变化的市场环境对产品需求量的影响,并达到降低成本的目的。这一问题便需要用多阶段设施规划（MFLP）的方法来解决。本文提出了一种改进的混和蚁群算法（HACO）来解决带有财务预算约束的多阶段设施规划问题,并将此方法与其他一些典型的启发式算法进行了对比分析。结果表明,本文提出的HACO算法是求解带有财务预算约束的MFLP问题的一种有效的方法。     

Heuristic Procedures for Practical-Sized Uncapacitated Location-Capacitated Routing Problems*

Facility location and vehicle routing are two important logistical problems closely interrelated in many real-world applications where locating facilities and determining the associated multi-stop vehicle routes are required simultaneously. Previous research has found that using the classical facility location models on these location-routing problems (LRPs) may lead to suboptimal solutions. We propose an approximate approach for the LRPs, which first generates and improves feasible location/allocation schemes with the associated multi-stop routing costs approximated using some route length estimators. We then design the minimum-cost routes based on the location/allocation results. We review two estimators that can provide accurate approximations to the multi-stop route distances; define the uncapacitated location-capacitated routing problem; and evaluate several heuristic procedures for approximately solving the problem. Computational results show that when vehicle capacities are not too restrictive, the sequential procedures that incorporate the two robust route length estimators can produce good solutions to practical-sized problems with a reasonable amount of computational efforts.     

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.     

Some inverse min-max network problems under weighted l1 and l∞ norms with bound constraints on changes

We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the deviation of the weights, measured by the weighted l ₁ norm or weighted l _∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree problem and the inverse maximum capacity path problem.     

基于双层规划的反恐应急设施选址模型及算法

恐怖袭击常以人流密集地区的平民作为袭击目标，并存在突发性和随机性等特点，极易造成严重的袭击后果。通过反恐应急设施的合理布局可以缩短救援人员和物资的到达时间，从而减轻袭击后果。首先，对反恐应急设施选址问题进行描述，并将其构造为一类离散双层规划模型。其中，上层规划是关于政府选址的0-1规划问题，下层规划则是关于恐怖分子袭击目标选择的0-1规划问题。其次，结合模型和问题的特征设计算法，利用分支定界算法实现上层选址变量的隐枚举，同时通过下层问题的求解来确定上下界并判断是否满足分枝或剪枝的条件。最后，结合南疆地区的交通拓扑网络进行算例分析，结果证明有效的选址方案可以大大降低袭击损失。     

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

Facility Location with Dynamic Distance Functions

Facility location problems have always been studied with theassumption that the edge lengths in the network are static anddo not change over time. The underlying network could be used to model a city street networkfor emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to trafficcongestion the traversal time on links changes with time. Very often, we have estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) ascenters, such that at every time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results forthe K-center problem under this model. This is the first comprehensive study regarding approximation algorithmsfor facility location for good time-invariant solutions.     

Approximation Algorithms for Bounded Facility Location Problems

The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.     

Attacking the Market Split Problem with Lattice Point Enumeration

The market split problem was proposed by Cornuéjols and Dawande as benchmark problem for algorithms solving linear systems with 0/1 variables. Here, we present an algorithm for the more general problem A · x = b with arbitrary lower and upper bound on the variables. The algorithm consists of exhaustive enumeration of all points of a suitable lattice which are contained in a given polyhedron. We present results for the feasibility version as well as for the integer programming version of the market split problem which indicate that the algorithm outperforms the previously published approaches to this problems considerably.     

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

Inverse maximum flow problems under the weighted Hamming distance

In this paper, we consider inverse maximum flow problem under the weighted Hamming distance. Four models are studied: the problem under sum-type weighted Hamming distance; the problem under bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times.Research supported by the National Natural Science Foundation of China (60021201), and the Hong Kong Research Grant Council under CERG CityU 9041091 and CUHK 103105.     

New algorithms for k-center and extensions

The problem of interest is covering a given point set with homothetic copies of several convex containers C ₁,…,C _k , while the objective is to minimize the maximum over the dilatation factors. Such k-containment problems arise in various applications, e.g. in facility location, shape fitting, data classification or clustering. So far most attention has been paid to the special case of the Euclidean k-center problem, where all containers C _i are Euclidean unit balls. Recent developments based on so-called core-sets enable not only better theoretical bounds in the running time of approximation algorithms but also improvements in practically solvable input sizes. Here, we present some new geometric inequalities and a Mixed-Integer-Convex-Programming formulation. Both are used in a very effective branch-and-bound routine which not only improves on best known running times in the Euclidean case but also handles general and even different containers among the C _i .     

ON PREDICTING COMPUTATIONAL TIME OF A BRANCH AND BOUND ALGORITHM FOR THE ASSIGNMENT OF FACILITIES

Experience with branch and bound algorithms indicates that computational time is a function of not only the size of the problem, but also the nature of the input data. This paper formulates statistically-based variables which describe certain characteristics of the input data and experimentally evaluates their ability to predict computational time for one branch and bound algorithm, the relative location of facilities or “plant layout” problem. Results suggest that the described experimental procedure may be useful for an a priori assessment of the computational difficulty of specific branch and bound problems.     

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.     

A Bicriterion Maximal Covering Location Formulation Which Considers the Satisfaction of Uncovered Demand

There have been many applications of the maximal covering location problem (MCLP). An underlying assumption of the MCLP is that demand not covered (i.e., not within a prespecified maximal distance of a facility) is not served. This may be an unrealistic assumption in many location planning scenarios, especially in the public sector. For example, in cases such as fire protection or ambulance service, calls not technically covered will still be serviced. The MCLP, however, does not consider the distances or travel times necessary to service such demand. This paper presents a bicriterion locational covering model which explicitly considers the travel distance or time necessary to service demand not within the maximal covering distance of a facility. The model may be used to generate noninferior (Pareto optimal) siting configurations which demonstrate the inherent trade-offs between a siting scheme designed to maximize total coverage and one designed to minimize total travel time for uncovered demand to reach its nearest facility. In addition, it is shown that for any particular weighting scheme on the two objectives, the problem can be solved as a p-median problem; a problem for which several efficient solution methods exist.