The rectilinear distance Weber problem in the presence of a probabilistic line barrier

This paper considers the problem of locating a single facility in the presence of a line barrier that occurs randomly on a given horizontal route on the plane. The objective is to locate this new facility such that the sum of the expected rectilinear distances from the facility to the demand points in the presence of the probabilistic barrier is minimized. Some properties of the problem are reported, a solution algorithm is provided with an example problem, and some future extensions to the problem are discussed.     

On the convergence of the Weiszfeld algorithm for continuous single facility location–allocation problems

A general family of single facility continuous location–allocation problems is introduced, which includes the decreasingly weighted ordered median problem, the single facility Weber problem with supply surplus, and Weber problems with alternative fast transportation network. We show in this paper that the extension of the well known Weiszfeld iterative decrease method for solving the corresponding location problems with fixed allocation yields an always convergent scheme for the location allocation problems. In a generic way, from each starting point, the limit point will be a locally minimal solution, whereas for each possible exceptional situation, a possible solution is indicated. Some computational results are presented, comparing this method with an alternating location–allocation approach. The research of the second author was partially supported by the grant of the Algerian Ministry of High Education 001BIS/PNE/ENSEIGNANTS/BELGIQUE.     

On an open problem in spherical facility location

In this paper we partially resolve an open problem in spherical facility location. The spherical facility location problem is a generalization of the planar Euclidean facility location problem. This problem was first studied by Katz and Cooper and by Drezner and Wesolowsky where a Weszfeld-like algorithm was proposed. This algorithm is very simple and does not require a line search. However, its convergence has been an open problem for more than ten years. In this paper, we prove that the sequence generated by the algorithm converges to the unique optimal solution under the condition that the oscillation of the sequence converges to zero. We conjecture that the algorithm is a descent algorithm and prove that the sequence generated by the algorithm converges to the optimal solution under this conjecture.     

On the convergence of a modified algorithm for the spherical facility location problem

We study the spherical facility location problem which is a more realistic model than the Euclidean facilities location. We present a modified algorithm for this problem, which has the following good properties: (a) It is very easy to initialize the algorithm with an arbitrary point as its starting point; (b) Under suitable assumptions, it is proved that the algorithm globally converges to a global minimizer of the problem.     

On the point for which the sum of the distances to <Emphasis Type="Italic">n</Emphasis> given points is minimum

Translation with annotations of E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tôhoku Mathematical Journal (first series), 43 (1937) pp. 355–386.A short introduction about the translation is found in Appendix A. Appendix B lists particular notations used by Weiszfeld and their now more conventional equivalents. Numbered footnotes are those of the original paper of Weiszfeld. Boxed numerals are references to observations about the translation and comments of the translator, all to be found in Appendix C.     

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

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

A BSSS algorithm for the single facility location problem in two regions with different norms

Suppose the plane is divided by a straight line into two regions with different norms. We want to find the location of a single new facility such that the sum of the distances from the existing facilities to this point is minimized. This is in fact a non-convex optimization problem. The main difficulty is caused by finding the distances between points on different sides of the boundary line. In this paper we present a closed form solution for finding these distances. We also show that the optimal solution lies in the rectangular hull of the existing points. Based on these findings then, an efficient big square small square (BSSS) procedure is proposed.     

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.     

On the coerciveness of some merit functions for complementarity problems over symmetric cones

One of the popular solution methods for the complementarity problem over symmetric cones is to reformulate it as the global minimization of a certain merit function. An important question to be answered for this class of methods is under what conditions the level sets of the merit function are bounded (the coerciveness of the merit function). In this paper, we introduce the generalized weak-coerciveness of a continuous transformation. Under this condition, we prove the coerciveness of some merit functions, such as the natural residual function, the normal map, and the Fukushima-Yamashita function for complementarity problems over symmetric cones. We note that this is a much milder condition than strong monotonicity, used in the current literature.     

On the use of the rotation minimizing frame for variational systems with Euclidean symmetry

We study variational systems for space curves, for which the Lagrangian or action principle has a Euclidean symmetry, using the Rotation Minimizing frame, also known as the Normal, Parallel, or Bishop frame. Such systems have previously been studied using the Frenet–Serret frame. However, the Rotation Minimizing frame has many advantages, and can be used to study a wider class of examples. We achieve our results by extending the powerful symbolic invariant calculus for Lie group–based moving frames, to the Rotation Minimizing frame case. To date, the invariant calculus has been developed for frames defined by algebraic equations. By contrast, the Rotation Minimizing frame is defined by a differential equation. In this paper, we derive the recurrence formulae for the symbolic invariant differentiation of the symbolic invariants. We then derive the syzygy operator needed to obtain Noether's conservation laws as well as the Euler–Lagrange equations directly in terms of the invariants, for variational problems with a Euclidean symmetry. We show how to use the six Noether laws to ease the integration problem for the minimizing curve, once the Euler–Lagrange equations have been solved for the generating differential invariants. Our applications include variational problems used in the study of strands of proteins, nucleid acids, and polymers.     

On the convergence of the sequence of solutions for a family of eigenvalue problems

The asymptotic behavior of the sequence {u _n } of positive first eigenfunctions for a class of eigenvalue problems is studied in a bounded domain with smooth boundary ? Ω. We prove , where δ is the distance function to ? Ω. Our study complements some earlier results by Payne and Philippin, Bhattacharya, DiBenedetto, and Manfredi, and Kawohl obtained in relation with the “torsional creep problem .”     

On the existence of convex classical solutions for multilayer free boundary problems with general nonlinear joining conditions

We prove the existence of convex classical solutions for a general multidimensional, multilayer free-boundary problem. The geometric context of this problem is a nested family of closed, convex surfaces. Except for the innermost and outermost surfaces, which are given, these surfaces are interpreted as unknown layer-interfaces, where the layers are the bounded annular domains between them. Each unknown interface is characterized by a quite general nonlinear equation, called a joining condition, which relates the first derivatives (along the interface) of the capacitary potentials in the two adjoining layers, as well as the spatial variables. A well-known special case of this problem involves several stationary, immiscible, two-dimensional flows of ideal fluid, related along their interfaces by Bernoulli's law.

     

On the weak solution of the Neumann problem for the 2D Helmholtz equation in a convex cone and Hs regularity

We extend previous results for the Neumann boundary value problem to the case of boundary data from the space $H^{-\frac{1}{2}+\varepsilon}(\Gamma), 0{<}{\varepsilon}{<}\frac{1}{2}We extend previous results for the Neumann boundary value problem to the case of boundary data from the space $H^{-\frac{1}{2}+\varepsilon}(\Gamma), 0{<}{\varepsilon}{<}\frac{1}{2}$, where Γ=?Ω is the boundary of a two‐dimensional cone Ω with angle β<π. We prove that for these boundary conditions the solution of the Helmholtz equation in Ω exists in the Sobolev space H^1+ε(Ω), is unique and depends continuously on the boundary data. Moreover, we give the Sommerfeld representation for these solutions. This can be used to formulate explicit compatibility conditions on the data for regularity properties of the corresponding solution. Copyright © 2010 John Wiley & Sons, Ltd.     

On the asymptotic behaviour of the eigenmodes for elliptic problems in domains becoming unbounded

The aim of this work is to analyze the asymptotic behaviour of the eigenmodes of some elliptic eigenvalue problems set on domains becoming unbounded in one or several directions. In particular, in the case of a linear elliptic operator in divergence form, we prove that the sequence of the -th eigenvalues convergences to the first eigenvalue of an elliptic problems set on the section of the domain. Moreover, an optimal rate of convergence of this sequence is given.

     

A tutorial on the use of graph coloring for some problems in robotics

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the location of the Entry/Exit station where the robot unloads the collected items after each trip along the corridor. The links of these systems with generalized coloring problems and other applications such that train shunting and pallet loading problems are discussed and related results are obtained. We conclude with several open questions on the topic.     

On the boundary value problem in a dihedral angle for normally hyperbolic systems of first order

Some structural properties as well as a general three-dimensional boundary value problem for normally hyperbolic systems of partial differential equations of first order are studied. A condition is given which enables one to reduce the system under consideration to a first-order system with the spliced principal part. It is shown that the initial problem is correct in a certain class of functions if some conditions are fulfilled.