An Efficient Genetic Algorithm for the p-Median Problem

We propose a new genetic algorithm for a well-known facility location problem. The algorithm is relatively simple and it generates good solutions quickly. Evolution is facilitated by a greedy heuristic. Computational tests with a total of 80 problems from four different sources with 100 to 1,000 nodes indicate that the best solution generated by the algorithm is within 0.1% of the optimum for 85% of the problems. The coding effort and the computational effort required are minimal, making the algorithm a good choice for practical applications requiring quick solutions, or for upper-bound generation to speed up optimal algorithms.     

Weak solutions to a nonlinear variational wave equation and some related problems

In this paper we present some results on the global existence of weak solutions to a nonlinear variational wave equation and some related problems. We first introduce the main tools, the L ^p Young measure theory and related compactness results, in the first section. Then we use the L ^p Young measure theory to prove the global existence of dissipative weak solutions to the asymptotic equation of the nonlinear wave equation, and comment on its relation to Camassa-Holm equations in the second section. In the third section, we prove the global existence of weak solutions to the original nonlinear wave equation under some restrictions on the wave speed. In the last section, we present global existence of renormalized solutions to two-dimensional model equations of the asymptotic equation, which is also the so-called vortex density equation arising from sup-conductivity.     

Heuristic Methods for Large Centroid Clustering Problems

This article presents new heuristic methods for solving a class of hard centroid clustering problems including the p-median, the sum-of-squares clustering and the multi-source Weber problems. Centroid clustering is to partition a set of entities into a given number of subsets and to find the location of a centre for each subset in such a way that a dissimilarity measure between the entities and the centres is minimized. The first method proposed is a candidate list search that produces good solutions in a short amount of time if the number of centres in the problem is not too large. The second method is a general local optimization approach that finds very good solutions. The third method is designed for problems with a large number of centres; it decomposes the problem into subproblems that are solved independently. Numerical results show that these methods are efficient—dozens of best solutions known to problem instances of the literature have been improved—and fast, handling problem instances with more than 85,000 entities and 15,000 centres—much larger than those solved in the literature. The expected complexity of these new procedures is discussed and shown to be comparable to that of an existing method which is known to be very fast.     

Nonlinear Dynamics Equation in p-Adic String Theory

We investigate nonlinear pseudodifferential equations with infinitely many derivatives. These are equations of a new class, and they originally appeared in p-adic string theory. Their investigation is of interest in mathematical physics and its applications, in particular, in string theory and cosmology. We undertake a systematic mathematical investigation of the properties of these equations and prove the main uniqueness theorem for the solution in an algebra of generalized functions. We discuss boundary problems for bounded solutions and prove the existence theorem for spatially homogeneous solutions for odd p. For even p, we prove the absence of a continuous nonnegative solution interpolating between two vacuums and indicate the possible existence of discontinuous solutions. We also consider the multidimensional equation and discuss soliton and q-brane solutions.     

Rough Isometry and <Emphasis Type="Italic">p</Emphasis>-Harmonic Boundaries of Complete Riemannian Manifolds

In this paper, we describe the behavior of bounded energy finite solutions for certain nonlinear elliptic operators on a complete Riemannian manifold in terms of its p-harmonic boundary. We also prove that if two complete Riemannian manifolds are roughly isometric to each other, then their p-harmonic boundaries are homeomorphic to each other. In the case, there is a one to one correspondence between the sets of bounded energy finite solutions on such manifolds. In particular, in the case of the Laplacian, it becomes a linear isomorphism between the spaces of bounded harmonic functions with finite Dirichlet integral on the manifolds. This work was supported by grant No. R06-2002-012-01001-0(2002) from the Basic Research Program of the Korea Science & Engineering Foundation.     

A new formulation for the conditional -median and -center problems

In this paper we discuss the conditional p-median and p-center problems on a network. Demand nodes are served by the closest facility whether existing or new. The formulation presented in this paper provided better results than those obtained by the best known formulation.     

Finite Energy Solutions of Maxwell''s Equations and Constructive Hodge Decompositions on Nonsmooth Riemannian Manifolds

We consider two basic potential theoretic problems in Riemannian manifolds: Hodge decompositions and Maxwell's equations. Here we are concerned with smoothness and integrability assumptions. In the context of L^p forms in Lipschitz domains, we show that both are well posed provided that 2−<p<2+, for some >0, depending on the domain. Our approach is constructive (in the sense that we produce integral representation formulas for the solutions) and emphasizes the intimate connections between the two problems at hand. Applications to other related PDEs, such as boundary problems for the Hodge Dirac operator, are also presented.     

Convexification of a Noninferior Frontier

In a recent paper by Li (Ref. 1), a scheme was proposed to convexify an efficient frontier for a vector optimization problem by rescaling each component of the vector objective functions by its p-power. For sufficiently large p, it was shown that the transformed efficient frontier is cone-convex; hence, the usual linear scalarization (or supporting hyperplane) method can be used to find the efficient solutions. An outstanding question remains: What is the minimum value of p such that the efficient frontier can be convexified? In this note, we answer the above question by deriving some theoretical lower bounds for p.

     

Applying simulated annealing to location-planning models

Simulated annealing is a computational approach that simulates an annealing schedule used in producing glass and metals. Originally developed by Metropolis et al. in 1953, it has since been applied to a number of integer programming problems, including the p-median location-allocation problem. However, previously reported results by Golden and Skiscim in 1986 were less than encouraging. This article addresses the design of a simulated-annealing approach for the p-median and maximal covering location problems. This design has produced very good solutions in modest amounts of computer time. Comparisons with an interchange heuristic demonstrate that simulated annealing has potential as a solution technique for solving location-planning problems and further research should be encouraged.     

Multiobjective routing problems

Summary Many network routing problems, particularly where the transportation of hazardous materials is involved, are multiobjective in nature; that is, it is desired to optimise not only physical path length but other features as well. Several such problems are defined here and a general framework for multiobjective routing problems is proposed. The notion of “efficient solution” is defined and it is demonstrated, by means of an example, that a problem may have very many solutions which are efficient. Next, potentially useful solution methods for multiobjective routing problems are discussed with emphasis being placed on the use of shortest/k-shortest path techniques. Finally, some directions for possible further research are indicated. Invited by B. Pelegrin     

On quasivariational inclusion problems of type I and related problems

The quasivariational inclusion problems are formulated and sufficient conditions on the existence of solutions are shown. As special cases, we obtain several results on the existence of solutions of a general vector ideal (proper, Pareto, weak) quasi-optimization problems, of quasivariational inequalities, and of vector quasi-equilibrium problems. Further, we prove theorems on the existence for solutions of the sum of these inclusions. As corollaries, we shall show several results on the existence of solutions to another problems in the vector optimization problems concerning multivalued mappings. This work was supported by the National Science Council of the Republic of China and the Academy of Sciences and Technologies of Vietnam. The authors wish to express their gratitude to the referees for their valuable suggestions.     

Gap Phenomena for p-Harmonic Maps

In this paper, we generalize to p-harmonic mapssome gap results known for harmonic maps. In particular, we prove that,under a certain level of energy depending on the curvature of the domainand target manifolds, the only p-harmonic maps are theconstant ones. The main tools are Bochner–Weitzenböck andReilly-type formulas involving the p-Laplace operator.     

On the Existence of Solutions of Quasi-equilibrium Problems with Constraints

The quasi-equilibrium problems with constraints are formulated and some sufficient conditions on the existence of their solutions are shown. As special cases, we obtain several results on the existence of solutions of some vector quasivariational inequality and vector optimization problems. An application of the obtained results is given to show the existence of solutions of quasi-optimization problems with constraints.     

含临界指数p-Kirchhoff型方程的非平凡解

本文研究了一类含临界指数的p-Kirchhoff型方程.利用变分方法与集中紧性原理,通过证明对应的能量泛函满足局部的(PS)_c条件,得到了这类方程非平凡解的存在性,推广了关于Kirchhoff型方程的相关结果.     

Aggregation error for location models: survey and analysis

Location problems occurring in urban or regional settings may involve many tens of thousands of “demand points,” usually individual private residences. In modeling such problems it is common to aggregate demand points to obtain tractable models. We survey aggregation approaches to a large class of location models, consider and compare various aggregation error measures, identify some effective (and ineffective) aggregation error measures, and discuss some open research areas.     

Analyticity of solutions of analytic non-linear general elliptic boundary value problems, and some results about linear problems

The main aim of this paper is to discuss the problem concerning the analyticity of the solutions of analytic non-linear elliptic boundary value problems. It is proved that if the corresponding first variation is regular in Lopatinskiĭ sense, then the solution is analytic up to the boundary. The method of proof really covers the case that the corresponding first variation is regularly elliptic in the sense of Douglis-Nirenberg-Volevich, and hence completely generalize the previous result of C. B. Morrey. The author also discusses linear elliptic boundary value problems for systems of elliptic partial differential equations where the boundary operators are allowed to have singular integral operators as their coefficients. Combining the standard Fourier transform technique with analytic continuation argument, the author constructs the Poisson and Green’s kernel matrices related to the problems discussed and hence obtain some representation formulae to the solutions. Some a priori estimates of Schauder type and L _p type are obtained. __________ Translated from Acta Sci. Natur. Univ. Jilin, 1963, (2): 403–447 by GAO Wenjie.     

Cooperative Parallel Variable Neighborhood Search for the p-Median

We propose a cooperative multi-search method for the Variable Neighborhood Search (VNS) meta-heuristic based on the central-memory mechanism that has been successfully applied to a number of difficult combinatorial problems. In this approach, several independent VNS meta-heuristics cooperate by asynchronously exchanging information about the best solutions identified so far, thus conserving the simplicity of the original, sequential VNS ideas. The p-median problem (PM) serves as test case. Extensive experimentations have been conducted on the classical TSPLIB benchmark problem instances with up to 11948 customers and 1000 medians, without any particular calibration of the parallel method. The results indicate that, compared to sequential VNS, the cooperative strategy yields significant gains in terms of computation time without a loss in solution quality.     

New results of periodic solutions for a kind of Duffing type p-Laplacian equation

By using Mawhin–Manásevich continuation theorem, some new sufficient conditions for the existence and uniqueness of periodic solutions of Duffing type p-Laplacian differential equation are established, which are complement of previously known results.     

Some heuristic methods for solving p-median problems with a coverage constraint

The aim of this paper is to solve p-median problems with an additional coverage constraint. These problems arise in location applications, when the trade-off between distance and coverage is being calculated. Three kinds of heuristic algorithms are developed. First, local search procedures are designed both for constructing and improving feasible solutions. Second, a multistart GRASP heuristic is developed, based on the previous local search methods. Third, by employing Lagrangean relaxation methods, a very efficient Lagrangean heuristic algorithm is designed, which extends the well known algorithm of Handler and Zang, for constrained shortest path problems, to constrained p-median problems. Finally, a comparison of the computational efficiency of the developed methods is made between a variety of problems of different sizes.     

The Cauchy problems for evolutionary pseudo-differential equations over p-adic field and the wavelet theory

We solve the Cauchy problems for p-adic linear and semi-linear evolutionary pseudo-differential equations (the time-variable t∈R and the space-variable ). Among the equations under consideration there are the heat type equation and the Schrödinger type equations (linear and nonlinear). To solve these problems, we develop the “variable separation method” (an analog of the classical Fourier method) which reduces solving evolutionary pseudo-differential equations to solving ordinary differential equations with respect to real variable t. The problem of stabilization for solutions of the Cauchy problems as t→∞ is also studied. These results give significant advance in the theory of p-adic pseudo-differential equations and can be used in applications.