Guided construction search metaheuristics for the capacitated p-median problem with single source constraint

In the capacitated p-median problem with single source constraint, also known as the capacitated clustering problem, a given set of n weighted points is to be partitioned into p clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centres that minimizes the total scatter of points allocated to these clusters. In this paper, a (λ, μ)-interchange neighbourhood based on the concept of λ-interchange of points restricted to μ-adjacent clusters is proposed. Structural properties of centres are identified and exploited to derive special data structures for their efficient evaluations. Different search and selection strategies including the variable neighbourhood search descent with respect to μ-nearest points are investigated. The most efficient strategies are then embedded in a guided construction search metaheuristic framework based either on a periodic local search procedure or a greedy random adaptive search procedure to solve the problem. Computational experience is reported on a standard set of benchmarks. The computational experience demonstrates the competitive performance of the proposed algorithms when compared to the best-known procedures in the literature in terms of solution quality and computational requirement.     

Approximate solutions of multiobjective optimization problems

This paper provides some new results on approximate Pareto solutions of a multiobjective optimization problem involving nonsmooth functions. We establish Fritz-John type necessary conditions and sufficient conditions for approximate Pareto solutions of such a problem. As a consequence, we obtain Fritz-John type necessary conditions for (weakly) Pareto solutions of the considered problem by exploiting the corresponding results of the approximate Pareto solutions. In addition, we state a dual problem formulated in an approximate form to the reference problem and explore duality relations between them.     

Eigenvalue analysis of constrained minimization problem for homogeneous polynomial

In this paper, the concepts of Pareto H-eigenvalue and Pareto Z-eigenvalue are introduced for studying constrained minimization problem and the necessary and sufficient conditions of such eigenvalues are given. It is proved that a symmetric tensor has at least one Pareto H-eigenvalue (Pareto Z-eigenvalue). Furthermore, the minimum Pareto H-eigenvalue (or Pareto Z-eigenvalue) of a symmetric tensor is exactly equal to the minimum value of constrained minimization problem of homogeneous polynomial deduced by such a tensor, which gives an alternative methods for solving the minimum value of constrained minimization problem. In particular, a symmetric tensor \({\mathcal {A}}\) is strictly copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is positive, and \({\mathcal {A}}\) is copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is non-negative.     

An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

Random extremal solutions of differential inclusions

Given a Lipschitz continuous multifunction F on \({\mathbb{R}^{n}}\), we construct a probability measure on the set of all solutions to the Cauchy problem \(\dot{x}\in F(x)\) with x(0) = 0. With probability one, the derivatives of these random solutions take values within the set extF(x) of extreme points for a.e. time t. This provides an alternative approach in the analysis of solutions to differential inclusions with non-convex right hand side.     

On ordered-covering mappings and implicit differential inequalities

We define the set of ordered covering of a mapping that acts in partially ordered spaces; we suggest a method for finding the set of ordered covering of vector functions of several variables and the Nemytskii operator acting in Lebesgue spaces. We prove assertions on operator inequalities in arbitrary partially ordered spaces. We obtain conditions that use a set of ordered covering of the corresponding mapping and ensure that the existence of an element u such that f(u) ≥ y implies the solvability of the equation f(x) = y and the estimate x ≤ u for its solution. We study the problem on the existence of the minimal and least solutions. These results are used for the analysis of an implicit differential equation. For the Cauchy problem, we prove a theorem on an inequality of the Chaplygin type.     

An approach to generate comprehensive piecewise linear interpolation of pareto outcomes to aid decision making

Multiple criteria decision making is a well established field encompassing aspects of search for solutions and selection of solutions in presence of more than one conflicting objectives. In this paper, we discuss an approach aimed towards the latter. The decision maker is presented with a limited number of Pareto optimal outcomes and is required to identify regions of interest for further investigation. The inherent sparsity of the given Pareto optimal outcomes in high dimensional space makes it an arduous task for the decision maker. To address this problem, an existing line of thought in literature is to generate a set of approximated Pareto optimal outcomes using piecewise linear interpolation. We present an approach within this paradigm, but one that delivers a comprehensive linearly interpolated set as opposed to its subset delivered by existing methods. We illustrate the advantage in doing so in comparison to stricter non-dominance conditions imposed in existing PAreto INTerpolation method. The interpolated set of outcomes delivered by the proposed approach are non-dominated with respect to the given Pareto optimal outcomes, and additionally the interpolated outcomes along uniformly distributed reference directions are presented to the decision maker. The errors in the given interpolations are also estimated in order to further aid decision making by establishing confidence in achieving true Pareto outcomes in their vicinity. The proposed approach for interpolation is computationally less demanding (for higher number of objectives) and also further amenable to parallelization. We illustrate the performance of the approach using six well established tri-objective test problems and two real-life examples. The problems span different types of fronts, such as convex, concave, mixed, degenerate, highlighting the wide applicability of the approach.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

Strong convergence theorem by a hybrid extragradient-like approximation method for variational inequalities and fixed point problems

The purpose of this paper is to investigate the problem of finding a common element of the set of fixed points F(S) of a nonexpansive mapping S and the set of solutions Ω _A of the variational inequality for a monotone, Lipschitz continuous mapping A. We introduce a hybrid extragradient-like approximation method which is based on the well-known extragradient method and a hybrid (or outer approximation) method. The method produces three sequences which are shown to converge strongly to the same common element of \({F(S)\cap\Omega_{A}}\). As applications, the method provides an algorithm for finding the common fixed point of a nonexpansive mapping and a pseudocontractive mapping, or a common zero of a monotone Lipschitz continuous mapping and a maximal monotone mapping.     

Persistence Barcodes Versus Kolmogorov Signatures: Detecting Modes of One-Dimensional Signals

We investigate the problem of estimating the number of modes (i.e., local maxima)—a well-known question in statistical inference—and we show how to do so without presmoothing the data. To this end, we modify the ideas of persistence barcodes by first relating persistence values in dimension one to distances (with respect to the supremum norm) to the sets of functions with a given number of modes, and subsequently working with norms different from the supremum norm. As a particular case, we investigate the Kolmogorov norm. We argue that this modification has certain statistical advantages. We offer confidence bands for the attendant Kolmogorov signatures, thereby allowing for the selection of relevant signatures with a statistically controllable error. As a result of independent interest, we show that taut strings minimize the number of critical points for a very general class of functions. We illustrate our results by several numerical examples.     

Local clustering coefficients in preferential attachment models

The local clustering coefficients of preferential attachment models are analyzed. Previously, a general approach to preferential attachment was proposed (the PA-class was introduced); it was shown that the degree distribution in all models of the PA-class obeys a power law. The global clustering coefficient was also analyzed, and a lower bound for the mean local clustering coefficient was found. In the paper, new results are obtained by analyzing the local clustering coefficients of models of the PA-class. Namely, the behavior of the mean value C ₂(n, d) of local clustering over vertices of degree d is studied.     

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.     

Conley index of nontrivial invariant sets in a Hilbert space

We study flows defined in a Hilbert space by potential completely continuous fields Id-K(·), where K(·) is an operator close to a homogeneous one. The Conley index of the set of fixed points and separatrices joining them (a nontrivial invariant set) is defined for such flows. By using this index, we prove that the equation K(x) = x has infinitely many solutions of arbitrarily large norm provided that the potential φ: ?φ(·) = K(·) is coercive and has an even leading part. As a corollary, we justify the stability of an arbitrary finite number of solutions under small perturbations of the field. We show that the Conley index differs from the classical rotation theory of vector fields when proving existence theorems.     

On the regularity of weak solutions to Burgers’ equation with finite entropy production

Bounded weak solutions of Burgers’ equation \(\partial _tu+\partial _x(u^2/2)=0\) that are not entropy solutions need in general not be BV. Nevertheless it is known that solutions with finite entropy productions have a BV-like structure: a rectifiable jump set of dimension one can be identified, outside which u has vanishing mean oscillation at all points. But it is not known whether all points outside this jump set are Lebesgue points, as they would be for BV solutions. In the present article we show that the set of non-Lebesgue points of u has Hausdorff dimension at most one. In contrast with the aforementioned structure result, we need only one particular entropy production to be a finite Radon measure, namely \(\mu =\partial _t (u^2/2)+\partial _x(u^3/3)\). We prove Hölder regularity at points where \(\mu \) has finite \((1+\alpha )\)-dimensional upper density for some \(\alpha >0\). The proof is inspired by a result of De Lellis, Westdickenberg and the second author : if \(\mu _+\) has vanishing 1-dimensional upper density, then u is an entropy solution. We obtain a quantitative version of this statement: if \(\mu _+\) is small then u is close in \(L^1\) to an entropy solution.     

Radar placement along banks of river

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k-Coverage RPPA problem (k-CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n ⁹) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn ⁵) dynamic programming algorithm for the k-CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)-time \({2\sqrt 2}\)-approximation algorithm for the RPPAS.     

Analysis of Local Search Landscapes for <Emphasis Type="Italic">k</Emphasis>-SAT Instances

Stochastic local search is a successful technique in diverse areas of combinatorial optimisation and is predominantly applied to hard problems. When dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase is helpful for an appropriate parameter adjustment of local search-based procedures. In the present paper, we address parameter estimations in the context of landscapes induced by k-SAT instances: at first, we utilise a sampling method devised by Garnier and Kallel in 2002 for approximations of the number of local maxima in landscapes generated by individual k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. The procedure provides good approximations of the actual number of local maxima, with a deviation typically around 10%. Secondly, we provide a method for obtaining upper bounds for the average number of local maxima in k-SAT instances. The method allows us to obtain the upper bound \(2^{n-O(\sqrt{n/k})}\) for the average number of local maxima, if m is in the region of 2 ^k · n/k.     

The convolution method for fourier expansions. The case of generalized transmission conditions of crack (screen) type in piecewise inhomogeneous media

We consider boundary value problems for the equation ? _x (K ? _x ?) + KL[?] = 0 in the space R ⁿ with generalized transmission conditions of the type of a strongly permeable crack or a weakly permeable screen on the surface x = 0. (Here L is an arbitrary linear differential operator with respect to the variables y ₁, …, y _n?1.) The coefficients K(x) > 0 are monotone functions of certain classes in the regions separated by the screen x = 0. The desired solution has arbitrary given singular points and satisfies a sufficiently weak condition at infinity.We derive formulas expressing the solutions of the above-mentioned problems in the form of simple quadratures via the solutions of the considered equation with a constant coefficient K for given singular points in the absence of a crack or a screen. In particular, the obtained formulas permit one to solve boundary value problems with generalized transmission conditions for equations with functional piecewise continuous coefficients in the framework of the theory of harmonic functions.     

Local bifurcations of plane running waves for the generalized cubic Schrödinger equation

For the generalized cubic Schrödinger equation, we consider a periodic boundary value problem in the case of n independent space variables. For this boundary value problem, there exists a countable set of plane running waves periodic with respect to the time variable. We analyze their stability and local bifurcations under the change of stability. We show that invariant tori of dimension 2, ..., n + 1 can bifurcate from each of them. We obtain asymptotic formulas for the solutions on invariant tori and stability conditions for bifurcating tori as well as parameter ranges in which, starting from n = 3, a subcritical (stiff) bifurcation of invariant tori is possible.     

A singular Monge-Ampère equation on unbounded domains

In this paper, we study the Dirichlet problem for a singular Monge-Amp`ere type equation on unbounded domains. For a few special kinds of unbounded convex domains, we find the explicit formulas of the solutions to the problem. For general unbounded convex domain ?, we prove the existence for solutions to the problem in the space C∞(?) ∩ C(?). We also obtain the local C1/2-estimate up to the ?? and the estimate for the lower bound of the solutions.     

Thick clusters for the radially symmetric nonlinear Schrödinger equation

This article is devoted to the study of radially symmetric solutions to the nonlinear Schrödinger equation

$\varepsilon^2 \Delta u - V(r)u + |u|^{p-1}u = 0\, {\rm in} B,\quad \frac{\partial u}{\partial n} = 0\, {\rm on}\,{\partial}B,$

where B is a ball in \({\mathbb{R}}^N\) , 1 <  p <  (N +  2)/(N ? 2), N ≥ 3 and the potential V is radially symmetric. We construct positive clustering solutions in an annulus having O(1/?) critical points, as well as sign changing solutions with O(1/?) zeroes concentrating near zero.