The directional p-median problem: Definition,complexity, and algorithms

An instance of a p-median problem gives n demand points. The objective is to locate p supply points in order to minimize the total distance of the demand points to their nearest supply point. p-Median is polynomially solvable in one dimension but NP-hard in two or more dimensions, when either the Euclidean or the rectilinear distance measure is used. In this paper, we treat the p-median problem under a new distance measure, the directional rectilinear distance, which requires the assigned supply point for a given demand point to lie above and to the right of it. In a previous work, we showed that the directional p-median problem is polynomially solvable in one dimension; we give here an improved solution through reformulating the problem as a special case of the constrained shortest path problem. We have previously proven that the problem is NP-complete in two or more dimensions; we present here an efficient heuristic to solve it. Compared to the robust Teitz and Bart heuristic, our heuristic enjoys substantial speedup while sacrificing little in terms of solution quality, making it an ideal choice for real-world applications with thousands of demand points.     

Exact pseudopolynomial algorithms for a balanced 2-clustering problem

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.     

Single facility location and relocation problem with time dependent weights and discrete planning horizon

In this paper a single facility location problem with multiple relocation opportunities is investigated. The weight associated with each demand point is a known function of time. We consider either rectilinear, or squared Euclidean, or Euclidean distances. Relocations can take place at pre-determined times. The objective function is to minimize the total location and relocation costs. An algorithm which finds the optimal locations, relocation times and the total cost, for all three types of distance measurements and various weight functions, is developed. Locations are found using constant weights, and relocations times are the solution to a Dynamic Programming or Binary Integer Programming (BIP) model. The time horizon can be finite or infinite.     

Bounds on the Optimal Location to the Weber Problem under Conditions of Uncertainty

Optimal and Heuristic bounds are given for the optimal location to the Weber problem when the locations of demand points are not deterministic but may be within given circles. Rectilinear, Euclidean and square Euclidean types of distance measure are discussed. The exact shape of all possible optimal points is given in the rectilinear and square Euclidean cases. A heuristic method for the computation of the region of possible optimal points is developed in the case of Euclidean distance problem. The maximal distance between a possible optimal point and the deterministic solution is also computed heuristically.     

Four-point Fermat location problems revisited. New proofs and extensions of old results

^** Email: frank.plastria{at}vub.ac.be What is the point at which the sum of (Euclidean) distancesto four fixed points in the plane is minimised? This extensionof the celebrated location question of Fermat about three pointswas partially solved by Fagnano around 1750, giving the followingsimple geometric answer: when the fixed points form a convexquadrangle it is the intersection point of both diagonals; itis not known who first derived the other case: otherwise itis the fixed point in the triangle formed by the three otherfixed points. We show that the first case extends and generalisesto general metric spaces, while the second case extends to anyplanar norm, any ellipsoidal norm in higher dimensional spacesand to the sphere. Received January 2005. accepted on 16 December 2005.     

On the complexity of some Euclidean optimal summing problems

The complexity status of several discrete optimization problems concerning the search for a subset of a finite set of Euclidean points (vectors) is analyzed. In the considered problems, the aim is to minimize objective functions depending either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is part of the input, then all analyzed problems are strongly NP-hard and, if the space dimension is fixed, then these problems are NP-hard even for dimension 2 (on a plane). It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension.     

Locating a minisum annulus: a new partial coverage distance model

The problem is to find the best location in the plane of a minisum annulus with fixed width using a partial coverage distance model. Using the concept of partial coverage distance, those demand points within the area of the annulus are served at no cost, while for ‘uncovered’ demand points there will be additional costs proportional to their distances to the annulus. The objective of the problem is to locate the annulus such that the sum of distances from the uncovered demand points to the annulus (covering area) is minimized. The distance is measured by the Euclidean norm. We discuss the case where the radius of the inner circle of the annulus is variable, and prove that at least two demand points must be on the boundary of any optimal annulus. An algorithm to solve the problem is derived based on this result.     

On the feasible set for the squared Euclidean Weber problem and applications

In this paper we find the set of feasible solution points to the Weber location problem with squared Euclidean distances when the weights can be at any point in a given set of intervals. We prove that this set is a convex polygon. The result is then used to solve the minimax regret objective when individual scenarios can be any set of weights in a given set of intervals.     

Linear facility location — Solving extensions of the basic problem

The basic problem is to locate a linear facility to minimize the sume of weighted shortest Euclidean distances from demand points to the facility. We extend the analysis to locating a constrained linear facility, a radial facility, a linear facility where distances are rectangular and a linear facility under the minimax criterion. Each case is shown to admit a simple solution technique.     

Fast approximations for sums of distances, clustering and the Fermat–Weber problem

We describe two data structures that preprocess a set S of n points in (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a factor of . This preprocessing technique has several applications in clustering and facility location. Using it, we derive an O(nlogn) time deterministic and O(n) time randomized -approximation algorithm for the so called Fermat–Weber problem in any fixed dimension.     

The planar hub location problem: a probabilistic clustering approach

Given the demand between each origin-destination pair on a network, the planar hub location problem is to locate the multiple hubs anywhere on the plane and to assign the traffic to them so as to minimize the total travelling cost. The trips between any two points can be nonstop (no hubs used) or started by visiting any of the hubs. The travel cost between hubs is discounted with a factor. It is assumed that each point can be served by multiple hubs. We propose a probabilistic clustering method for the planar hub-location problem which is analogous to the method of Iyigun and Ben-Israel (in Operations Research Letters 38, 207–214, 2010; Computational Optmization and Applications, 2013) for the solution of the multi-facility location problem. The proposed method is an iterative probabilistic approach assuming that all trips can be taken with probabilities that depend on the travel costs based on the hub locations. Each hub location is the convex combination of all data points and other hubs. The probabilities are updated at each iteration together with the hub locations. Computations stop when the hub locations stop moving. Fermat-Weber problem and multi-facility location problem are the special cases of the proposed approach.     

A new metaheuristic algorithm based on shark smell optimization

In this article, a new metaheuristic optimization algorithm is introduced. This algorithm is based on the ability of shark, as a superior hunter in the nature, for finding prey, which is taken from the smell sense of shark and its movement to the odor source. Various behaviors of shark within the search environment, that is, sea water, are mathematically modeled within the proposed optimization approach. The effectiveness of the suggested approach is compared with many other heuristic optimization methods based on standard benchmark functions. Also, to illustrate the efficiency of the proposed optimization method for solving real‐world engineering problems, it is applied for the solution of load frequency control problem in electrical power systems. The obtained results confirm the validity of the proposed metaheuristic optimization algorithm. © 2014 Wiley Periodicals, Inc. Complexity 21: 97–116, 2016     

The inverse Fermat–Weber problem

Given n points in the plane with nonnegative weights, the inverse Fermat–Weber problem consists in changing the weights at minimum cost such that a prespecified point in the plane becomes the Euclidean 1-median. The cost is proportional to the increase or decrease of the corresponding weight. In case that the prespecified point does not coincide with one of the given n points, the inverse Fermat–Weber problem can be formulated as linear program. We derive a purely combinatorial algorithm which solves the inverse Fermat–Weber problem with unit cost using O(n) greedy-like iterations where each of them can be done in constant time if the points are sorted according to their slopes. If the prespecified point coincides with one of the given n points, it is shown that the corresponding inverse problem can be written as convex problem and hence is solvable in polynomial time to any fixed precision.     

A maximumb-matching problem arising from median location models with applications to the roommates problem

We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

在闭凸集上连续型多场址的最优选择

本文考虑带有约束的连续型多场址问题(CEMFLC).对于连续型多场址问题(CEMFLC),我们给出了在闭集上选择最优场址的算法,证明了该算法是全局收敛的,最后,我们指出这一算法可用于解有约束或无约束的的高离散型多场址问题(EMFL),而且简化了(EMFL)问题现有的一些算法.     

Optimum inventory policies with discrete time proportional demand,discrete replenishment opportunities and different optimizing criteria

This paper extends the deterministic, single product, dynamic E0Q model to the case where demand increases linearly with time but at discrete time points and where the number of replenishments is also discrete. The problem is to find the number of orders and the replenishment schedule that will either maximize the return on the investment on inventory or minimize inventory costs. The proposed solution to either problem requires to first find the replenishment schedule that will minimize the total inventory throughout the planning horizon, for a given number of orders and then find the optimal number of replenishment points. The solution algorithms exploit the discrete nature of the demand and do not require the decomposability property of dynamic programming. This is particularly important in the return on investment case, where decomposability cannot be achieved.     

Heuristics for the fixed cost median problem

We describe in this paper polynomial heuristics for three important hard problems—the discrete fixed cost median problem (the plant location problem), the continuous fixed cost median problem in a Euclidean space, and the network fixed cost median problem with convex costs. The heuristics for all the three problems guarantee error ratios no worse than the logarithm of the number of customer points. The derivation of the heuristics is based on the presentation of all types of median problems discussed as a set covering problem.     

A globally convergent algorithm for the Euclidean multiplicity location problem

The Euclidean single facility location problem (ESFL) and the Euclidean multiplicity location problem (EMFL) are two special nonsmooth convex programming problems which have attracted a large literature. For the ESFL problem, there are algorithms which converge both globally and quadratically. For the EMFL problem, there are some quadratically convergent algorithms, but for global convergence, they all need nontrivial assumptions on the problem.In this paper, we present an algorithm for EMFL. With no assumption on the problem, it is proved that from any initial point, this algorithm generates a sequence of points which converges to the closed convex set of optimal solutions of EMFL.This research is supported in part by the Air Force Office of Scientific Research Grant AFOSR-87-0127, the National Science Foundation Grant DCR-8420935 and University of Minnesota Graduate School Doctoral Dissertation Fellowship awarded to G.L. Xue.     

Covering moving points with anchored disks

Consider a set of mobile clients represented by n points in the plane moving at constant speed along n different straight lines. We study the problem of covering all mobile clients using a set of k disks centered at k fixed centers. Each disk exists only at one instant and while it does, covers any client within its coverage radius. The task is to select an activation time and a radius for each disk such that every mobile client is covered by at least one disk. In particular, we study the optimization problem of minimizing the maximum coverage radius. First we prove that, although the static version of the problem is polynomial, the kinetic version is NP-hard. Moreover, we show that the problem is not approximable by a constant factor (unless P = NP). We then present a generic framework to solve it for fixed values of k, which in turn allows us to solve more general optimization problems. Our algorithms are efficient for constant values of k.     

HOLDITCH THEOREM FOR THE CLOSED SPACE CURVES IN LORENTZIAN 3-SPACE

In this article, we give the area formula of the closed projection curve of a closed space curve in Lorentzian 3-space L3. For the 1-parameter closed Lorentzian space motion in L3, we obtain a Holditch Theorem taking into account the Lorentzian matrix multiplication for the closed space curves by using their othogonal projections onto the Euclidean plane in the fixed Lorentzian space. Moreover, we generalize this Holditch Theorem for noncollinear three fixed points of the moving Lorentzian space and any other fixed point on the plane which is determined by these three fixed points.