The traveling salesman problem in graphs with some excluded minors

Given a graph and a length function defined on its edge-set, the Traveling Salesman Problem can be described as the problem of finding a family of edges (an edge may be chosen several times) which forms a spanning Eulerian subgraph of minimum length. In this paper we characterize those graphs for which the convex hull of all solutions is given by the nonnegativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given which uses a small number of basic graphs.     

An additive bounding procedure for the asymmetric travelling salesman problem

In this paper, new lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences. The new bounds are combined in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure (1981). Both procedures have been imbedded in a simple branch and bound algorithm and experimentally evaluated on hard test problems.     

A quadratic assignment formulation of the molecular conformation problem

The molecular conformation problem is discussed, and a concave quadratic global minimization approach for solving it is described. This approach is based on a quadratic assignment formulation of a discrete approximation to the original problem.     

The Cauchy Problem for a Class of Semilinear Wave Equations with Piecewise Constants Data

ＴｈｅＣａｕｃｈｙＰｒｏｂｌｅｍｆｏｒａＣｌａｓｓｏｆＳｅｍｉｌｉｎｅａｒＷａｖｅＥｑｕａｔｉｏｎｓｗｉｔｈＰｉｅｃｅｗｉｓｅＣｏｎｓｔａｎｔｓＤａｔａＺｈａｎｇＹｏｎｇｑｉａｎ（张永前）（ＩｎｓｔｉｔｕｔｅｏｆＭａｔｈｅｍａｔｉｃｓ，ＦｕｄａｎＵｎ...     

Network analysis of eigenvalue problem for multilayer dielectric waveguide consisting of arbitrary number of layers

In this paper, the eigenvalue problem of a multilayer dielectric waveguide consisting of arbitrary number of layers is solved by the microwave network method. A general program with the function of computer graphics has been developed for analyzing the dispersion characteristics and the electromagnetic field distributions of an N layer dielectric waveguide. As examples of practical applications of the program, first, the dispersions and field patterns for the planar waveguides with refractive index of parabolic and exponential profiles are analyzed. Secondly, the procedure of mode conversion and mode separation in dielectric branching waveguides is vividly demonstrated through analyzing the field distributions of asymmetric multilayer dielectric structures and the general rules of mode conversion are discussed. The examples show that the present method possesses the advantages of versatility, rapidity, simplicity and accuracy.     

A competitive (dual) simplex method for the assignment problem

Where there is abundance of mystery and confusion in every direction, the truth seldom remains hidden for long. It's a matter of having plenty of angles to go at it from. Only the utterly simple crimes - the simplex crimes, you may say - have the trick of remaining baffling. - Sir John (from Michael Innes,The Open House (A Sir John Appleby Mystery), Penguin Books, 1974).A dual simplex method for the assignment problem leaves open to choice the activity (i,j) of rowi and columnj that is to be dropped in pivoting so long asx _ij < 0. A choice (i,j) over columnsj having at least 3 basic activities that minimizesx _ij is shown to converge in at most ( ₂ ^n-1 ) pivots, and at most O(n ³) time, and it is argued that on average the number of pivots is at mostn logn. Dedicated with affection to George B. Dantzig on the occasion of his seventieth birthday.     

Children’s use of realistic considerations in problem solving: some English evidence

This is the second of two papers exploring children’s responses to an extended version of a division-with-remainder problem intended to elicit general rather than particular realistic considerations during mathematical problem solving. Responses to two problems are analyzed. The first is a ‘realistically’ contextualised item drawn from national tests in England whose ambiguities have been previously discussed (Cooper, 1992); the second is a version of this problem revised to encourage a wider range of realistic responses. In Cooper and Harries (2002), the responses of children at the end of their first year of secondary schooling were analyzed. Here the responses of children at the end of their primary schooling are analyzed and compared with the previous results. It is shown that many children, given suitable encouragement, are willing and able to enter into an extended form of realistic thinking during problem solving, although the original test item renders this invisible.     

“Painlevé 34” equation: Equivalence test

We give the complete solution of the Equivalence Problem for “Painlevé 34” equation.     

The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method

This paper focuses on vehicle routing problems with profits and addresses the so-called Capacitated Team Orienteering Problem. Given a set of customers with a priori known profits and demands, the objective is to find the subset of customers, for which the collected profit is maximized, and to determine the visiting sequence and assignment to vehicle routes assuming capacity and route duration restrictions. The proposed method adopts a hierarchical bi-level search framework that takes advantage of different search landscapes. At the upper level, the solution space is explored on the basis of the collected profit, using a Filter-and-Fan method and a combination of profit oriented neighborhoods, while at the lower level the routing of customers is optimized in terms of traveling distance via a Variable Neighborhood Descent method. Computational experiments on benchmark data sets illustrate the efficiency and effectiveness of the proposed approach. Compared to existing results, new upper bounds are produced with competitive computational times.     

Remarks on Barbashin-Ezeilo Problem on third-order nonlinear differential equations

In this paper, we use the frequency domain criteria to initiate a general result on the Barbashin-Ezeilo Problem on third-order nonlinear differential equation. Earlier ideas of Burkin [I.M. Burkin, Orbital stability of second-kind limiting cycles for dynamical systems with cylindrical phase space, Differential Equations 29 (1993) 1262-1264], Leonov [G.A. Leonov, A frequency criterion for the existence of limit cycles of dynamical systems with cylindrical phase spaces, Differential Equations 23 (1987) 1375-1378] on the problem are being improved upon.