A characterization of linear admissible transformations for the m-travelling salesmen problem

Some methods for solving the Multiple-Travelling Salesmen type of problems are based on certain transformations of the distances matrix. The transformed matrix entails a new objective function, for which an optimal solution is sought.This paper deals with these transformations and in it those which are valid in a linear context are analyzed. “Linear admissible transformations” are studied, with their characterization, and the more relevant transformations given by other authors when solving the Single-Travelling Salesman Problem and the Delivery Problem are discussed under this approach.     

Competitive travelling salesmen problem: A hyper-heuristic approach

We introduce a novel variant of the travelling salesmen problem and propose a hyper-heuristic methodology in order to solve it. In a competitive travelling salesmen problem (CTSP), m travelling salesmen are to visit n cities and the relationship between the travelling salesmen is non-cooperative. The salesmen will receive a payoff if they are the first one to visit a city and they pay a cost for any distance travelled. The objective of each salesman is to visit as many unvisited cities as possible, with a minimum travelling distance. Due to the competitive element, each salesman needs to consider the tours of other salesman when planning their own tour. Since equilibrium analysis is difficult in the CTSP, a hyper-heuristic methodology is developed. The model assumes that each agent adopts a heuristic (or set of heuristics) to choose their moves (or tour) and each agent knows that the moves/tours of all agents are not necessarily optimal. The hyper-heuristic consists of a number of low-level heuristics, each of which can be used to create a move/tour given the heuristics of the other agents, together with a high-level heuristic that is used to select from the low-level heuristics at each decision point. Several computational examples are given to illustrate the effectiveness of the proposed approach.     

On rational transformations of linear functionals: direct problem

Let u be a quasi-definite linear functional. We find necessary and sufficient conditions in order to the linear functional v satisfying be a quasi-definite one. Also we analyze some linear relations linking the polynomials orthogonal with respect to u and v.     

A characterization of linear transformations which leave the doubly stochastic matrices

A characterization of linear transformations which leave the n×n doubly stochastic matrices invariant is given as a linear combination of functions of the type T(X)=AXB with certain restrictions posed on the n×n matrices A and B.     

A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms

This paper proposes a new crossover operator called two-part chromosome crossover (TCX) for solving the multiple travelling salesmen problem (MTSP) using a genetic algorithm (GA) for near-optimal solutions. We adopt the two-part chromosome representation technique which has been proven to minimise the size of the problem search space. Nevertheless, the existing crossover method for the two-part chromosome representation has two limitations. Firstly, it has extremely limited diversity in the second part of the chromosome, which greatly restricts the search ability of the GA. Secondly, the existing crossover approach tends to break useful building blocks in the first part of the chromosome, which reduces the GA’s effectiveness and solution quality. Therefore, in order to improve the GA search performance with the two-part chromosome representation, we propose TCX to overcome these two limitations and improve solution quality. Moreover, we evaluate and compare the proposed TCX with three different crossover methods for two MTSP objective functions, namely, minimising total travel distance and minimising longest tour. The experimental results show that TCX can improve the solution quality of the GA compared to three existing crossover approaches.     

A stability result for the magnetic shaping problem

We consider the bidimensional magnetic shaping problem without surface tension and study its stability when the boundary of the domain has cusp points. We show in particular that one has stability when the curvature of the smooth parts of is negative.     

A multiplicity result for the jumping nonlinearity problem

We consider a class of nonlinear problems of the form Au+g(x,u)=f, where A is an unbounded self-adjoint operator on a Hilbert space H of L2(Ω)-functions, an arbitrary domain, and is a “jumping nonlinearity” in the sense that the limits , exist and “jump” over the principal eigenvalue of the operator −A. Under rather general conditions on the operator L and for suitable a<b, we prove some multiplicity results. Applications are given to the wave equation, and elliptic equations in the whole space .     

A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree

Given an edge-weighted tree T and an integer p1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2−2/(p+1))-approximation algorithm which runs in O(p^p−1n^p−1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p−1)!·n) time.     

A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem

Under study is the maximum 2 peripatetic salesmen problem which consists in finding two edge-disjoint Hamiltonian cycles with maximal total weight in a complete undirected graph. We present a cubic time approximation algorithm for this problem with the performance guarantee 7/9 which is the best known estimation by now. We also present a modification of this algorithm for the case when the weights of graph edges are values in a given range [1, q] with the performance guarantee (7q + 3)/(9q + 1) which is also the best known estimation by now and has cubic time complexity too.     

A uniqueness result for a semilinear elliptic problem: A computer-assisted proof

Starting with the famous article [A. Gidas, W.M. Ni, L. Nirenberg, Symmetry and related properties via the maximum principle, Comm. Math. Phys. 68 (1979) 209-243], many papers have been devoted to the uniqueness question for positive solutions of −Δu=λu+up in Ω, u=0 on ∂Ω, where p>1 and λ ranges between 0 and the first Dirichlet eigenvalue λ₁(Ω) of −Δ. For the case when Ω is a ball, uniqueness could be proved, mainly by ODE techniques. But very little is known when Ω is not a ball, and then only for λ=0. In this article, we prove uniqueness, for all λ∈[0,λ₁(Ω)), in the case Ω=²(0,1) and p=2. This constitutes the first positive answer to the uniqueness question in a domain different from a ball. Our proof makes heavy use of computer assistance: we compute a branch of approximate solutions and prove existence of a true solution branch close to it, using fixed point techniques. By eigenvalue enclosure methods, and an additional analytical argument for λ close to λ₁(Ω), we deduce the non-degeneracy of all solutions along this branch, whence uniqueness follows from the known bifurcation structure of the problem.     

A new result on the Pompeiu problem

A nonempty bounded open set () is said to have the Pompeiu property if and only if the only continuous function on for which the integral of over is zero for all rigid motions of is . We consider a nonempty bounded open set with Lipschitz boundary and we assume that the complement of is connected. We show that the failure of the Pompeiu property for implies some geometric conditions. Using these conditions we prove that a special kind of solid tori in , , has the Pompeiu property. So far the result was proved only for solid tori in . We also examine the case of planar domains. Finally we extend the example of solid tori to domains in bounded by hypersurfaces of revolution.

     

A stability result concerning the obstacle problem for a plate

It is proposed here to study the free boundary of the obstacle problem in the case of an elastic plate. Under a nondegeneracy assumption, we prove a stability theorem which relates the variations of the contact zone to the variations the external forces. The statement of this result obtained and the steps in the proof are very close to those given by D.G. Schaeffer in 1975, except for the very important fact that the present study deals with the biharmonic operator.     

A neural network for the linear complementarity problem

An artificial neural network is proposed in this paper for solving the linear complementarity problem. The new neural network is based on a reformulation of the linear complementarity problem into the unconstrained minimization problem. Our new neural network can be easily implemented on a circuit. On the theoretical aspect, we analyze the existence of the equilibrium points for our neural network. In addition, we prove that if the equilibrium point exists for the neural network, then any such equilibrium point is both asymptotically and bounded (Lagrange) stable for any initial state. Furthermore, linear programming and certain quadratical programming problems (not necessarily convex) can be also solved by the neural network. Simulation results on several problems including a nonconvex one are also reported.     

A new equation for the linear regulator problem

In this article, a new equation is derived for the optimal feedback gain matrix characterizing the solution of the standard linear regulator problem. It will be seen that, in contrast to the usual algebraic Riccati equation which requires the solution ofn(n + 1)/2 quadratically nonlinear algebraic equations, the new equation requires the solution of onlynm such equations, wherem is the number of system input terminals andn is the dimension of the state vector of the system. Utilizing the new equation, results are presented for the inverse problem of linear control theory.