Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

A New Method for the Multifacility Minimax Location Problem

This paper presents a new method of locating n new facilities among m destinations in accordance with the minimax criterion; that is, the facilities are located to minimize the maximum weighted distance in the system. Distances may be rectangular, Euclidean, or general (l _p ). The method involves the numerical integration of ordinary differential equations and is computationally superior to methods using nonlinear programming.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

Set covering location models with stochastic critical distances

This paper formulates a new version of set covering models by introducing a customer-determined stochastic critical distance. In this model, all services are provided at the sites of facilities, and customers have to go to the facility sites to obtain the services. Due to the randomness of their critical distance, customers patronize a far or near facility with a probability. The objective is to find a minimum cost set of facilities so that every customer is covered by at least one facility with an average probability greater than a given level α. We consider an instance of the problem by embedding the exponential effect of distance into the model. An algorithm based on two searching paths is proposed for solutions to the instance. Experiments show that the algorithm performs well for problems with greater α, and the experimental results for smaller α are reported and analysed.     

Properties and Solution Methods for Large Location—Allocation Problems

Location-allocation with l _p distances is studied. It is shown that this structure can be expressed as a concave minimization programming problem. Since concave minimization algorithms are not yet well developed, five solution methods are developed which utilize the special properties of the location-allocation problem. Using the rectilinear distance measure, two of these algorithms achieved optimal solutions in all 102 test problems for which solutions were known. The algorithms can be applied to much larger problems than any existing exact methods.     

Three-Webs Defined by Symmetric Functions

We study local differential-geometrical properties of curvilinear k-webs defined by symmetric functions (webs SW(k)). This class of k-webs contains in particular algebraic rectilinear k-webs defined by algebraic curves of genus 0. On a web SW(3), there are three three-parameter families of closed Thomsen configurations. We find equations of a rectilinear web SW(k) in terms of adapted coordinates and prove that the curvature of a symmetric three-web is a skew-symmetric function with respect to adapted coordinates. In conclusion, we formulate some open problems.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

Minimum Energy Problem on the Hypersphere

We consider the minimum energy problem on the unit sphere \(\mathbb {S}^{d-1}\) in the Euclidean space \(\mathbb {R}^{d}\), d = 3, in the presence of an external field Q, where the charges are assumed to interact according to Newtonian potential 1/r ^d-2, with r denoting the Euclidean distance. We solve the problem by finding the support of the extremal measure, and obtaining an explicit expression for the density of the extremal measure. We then apply our results to an external field generated by a point charge of positive magnitude, placed at the North Pole of the sphere, and to a quadratic external field.     

Minimal Translation Hypersurfaces in Euclidean Space

The graph of a function f defined in some open set of the Euclidean space of dimension (p + q) is said to be a translation graph if f may be expressed as the sum of two independent functions ? and ψ defined in open sets of the Euclidean spaces of dimension p and q, respectively. We obtain a useful expression for the mean curvature of the graph of f in terms of the Laplacian, the gradient of ? and ψ as well as of the mean curvatures of their graphs. We study translation graphs having zero mean curvature, that is, minimal translation graphs, by imposing natural conditions on ? and ψ, like harmonicity, minimality and eikonality (constant norm of the gradient), giving several examples as well as characterization results.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n ³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}{{\ln n}}\), respectively.     

An Uncertainty Principle of Paley and Wiener on Euclidean Motion Group

A classical result due to Paley and Wiener characterizes the existence of a non-zero function in \(L^2(\mathbb {R}),\) supported on a half line, in terms of the decay of its Fourier transform. In this paper we prove an analogue of this result for compactly supported continuous functions on the Euclidean motion group M(n). We also relate this result to a unique continuation property of solutions to the initial value problem for time-dependent Schrödinger equation on M(n).     

Consistent Digital Rays

Given a fixed origin o in the d-dimensional grid, we give a novel definition of digital rays dig(op) from o to each grid point p. Each digital ray dig(op) approximates the Euclidean line segment \(\overline {op}\) between o and p. The set of all digital rays satisfies a set of axioms analogous to the Euclidean axioms. We measure the approximation quality by the maximum Hausdorff distance between a digital ray and its Euclidean counterpart and establish an asymptotically tight Θ(log?n) bound in the n×n grid. The proof of the bound is based on discrepancy theory and a simple construction algorithm. Without a monotonicity property for digital rays the bound is improved to O(1). Digital rays enable us to define the family of digital star-shaped regions centered at o, which we use to design efficient algorithms for image processing problems.     

Euclidean and Hermitian LCD MDS codes

Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. On the other hand, being optimal codes, maximum distance separable codes (abbreviated MDS) are of much interest from many viewpoints due to their theoretical and practical properties. However, little work has been done on LCD MDS codes. In particular, determining the existence of q-ary [n, k] LCD MDS codes for various lengths n and dimensions k is a basic and interesting problem. In this paper, we firstly study the problem of the existence of q-ary [n, k] LCD MDS codes and solve it for the Euclidean case. More specifically, we show that for \(q>3\) there exists a q-ary [n, k] Euclidean LCD MDS code, where \(0\le k \le n\le q+1\), or, \(q=2^{m}\), \(n=q+2\) and \(k= 3 \text { or } q-1\). Secondly, we investigate several constructions of new Euclidean and Hermitian LCD MDS codes. Our main techniques in constructing Euclidean and Hermitian LCD MDS codes use some linear codes with small dimension or codimension, self-orthogonal codes and generalized Reed-Solomon codes.     

Holomorphic Minorants of Plurisubharmonic Functions

Let φ be a plurisubharmonic function on a pseudoconvex domain D in an n-dimensional complex space. We show that there exists a nonzero holomorphic function f on D such that some local mean value of φ with logarithmic additional terms majorizes log|f|. A similar problem is discussed for a locally integrable function on D in terms of balayage of positive measures.     

Consistent and Inconsistent Rules in Competitive Facility Choice

Competitive facility location models are based on the assumption that customers select a facility to patronize according to some rule involving the distance to the facility. A customer prefers facility A over facility B if the distance to facility A is shorter than some function of the distance to facility B. We define a consistency property of a selection rule. A selection rule is consistent if the selection of a facility remains unchanged along the shortest route to that facility: namely the rule cannot indicate a preference for a different facility while en route to the selected one. Otherwise, the rule is inconsistent. We prove that under mild conditions, the only consistent rule is the one based on an additive function of the distance, a function which is the sum of the distance and a constant. All other rules, such as a product of the distance and a constant (a multiplicative function), are inconsistent.     

Asymptotics of the Velocity Potential of an Ideal Fluid Flowing around a Thin Body

We consider the Neumann problem outside a small neighborhood of a planar disk in the three-dimensional space. The surface of this neighborhood is assumed to be smooth, and its thickness is characterized by a small parameter ε. A uniform asymptotic expansion of the solution of this problem with respect to ε is constructed by the matching method. Since the problem turned out to be bisingular, an additional inner asymptotic expansion in the so-called stretched variables is constructed near the edge of the disk. A physical interpretation of the solution of this boundary value problem is the velocity potential of a laminar flow of an ideal fluid around a thin body, which is the neighborhood of the disk. It is assumed that this flow has unit velocity at a large distance from the disk, which is equivalent to the following condition for the potential: u(x₁, x₂, x₃, ε) = x₃+O(r^?2) as r → ∞, where r is the distance to the origin. The boundary condition of this problem is the impermeability of the surface of the body: ?u/?n = 0 at the boundary. After subtracting x₃ from the solution u(x₁, x₂, x₃, ε), we get a boundary value problem for the potential ?(x₁, x₂, x₃, ε) of the perturbed motion. Since the integral of the function ??/?n over the surface of the body is zero, we have ?(x₁, x₂, x₃, ε) = O(r^?2) as r → ∞. Hence, all the coefficients of the outer asymptotic expansion with respect to ε have the same behavior at infinity. However, these coefficients have growing singularities at the approach to the edge of the disk, which implies the bisingularity of the problem.