On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

Analysis of crossovers and selections in a coarse-grained parallel genetic algorithm

The parallel genetic algorithms (PGA) have been developed for combinatorial optimization problems, and its parallel efficiencies have been investigated on a specific problem. These investigations were concerned with how to design a topology and the determination of the optimum setting for parameters (for example, size of subpopulations, migration interval, and so on) rather than the effectiveness of genetic operators. This paper investigates a relation between the parallel efficiency of the coarse-grained PGA and genetic (crossover and selection) operators for the traveling salesman problem on an MIMD parallel computer. The following genetic operators are considered: improved edge recombination (IERX), distance preserving (DPX), and complete subtour exchange (CSEX) crossovers, and two selection operators, which have relatively high selection pressures. Computational results indicate that the parallel efficiency is significantly affected by the difference of crossovers rather than the selections, and the PGA with CSEX gives better properties.     

Classification of Traveling Waves for a Class of Nonlinear Wave Equations

We classify the weak traveling wave solutions for a class of one-dimensional non-linear shallow water wave models. The equations are shown to admit smooth, peaked, and cusped solutions, as well as more exotic waves such as stumpons and composite waves. We also explain how some previously studied traveling wave solutions of the models fit into this classification.     

Traveling waves of an elliptic-hyperbolic model of phase transitions via varying viscosity-capillarity

We consider an elliptic-hyperbolic model of phase transitions and we show that any Lax shock can be approximated by a traveling wave with a suitable choice of viscosity and capillarity. By varying viscosity and capillarity coefficients, we can cover any Lax shock which either remains in the same phase, or admits a phase transition. The argument used in this paper extends the one in our earlier works. The method relies on LaSalle?s invariance principle and on estimating attraction region of the asymptotically stable of the associated autonomous system of differential equations. We will show that the saddle point of this system of differential equations lies on the boundary of the attraction region and that there is a trajectory leaving the saddle point and entering the attraction region. This gives us a traveling wave connecting the two states of the Lax shock. We also present numerical illustrations of traveling waves.     

George Dantzig’s contributions to integer programming

This paper reviews George Dantzig’s contributions to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem.     

Certification of an optimal TSP tour through 85,900 cities

We describe a computer code and data that together certify the optimality of a solution to the 85,900-city traveling salesman problem pla85900, the largest instance in the TSPLIB collection of challenge problems.     

A new formulation for the Traveling Deliveryman Problem

The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree.     

Uniqueness of traveling wave solutions for a biological reaction-diffusion equation

The existence of traveling wave solutions for a reaction-diffusion, which serves as models for microbial growth in a flow reactor and for mathematical epidemiology, was previously confirmed. However, the problem on the uniqueness of traveling wave solutions remains open. In this paper we give a complete proof of the uniqueness of traveling wave solutions.     

Maximizing breaks and bounding solutions to the mirrored traveling tournament problem

We investigate the relation between two aspects of round robin tournament scheduling problems: breaks and distances. The distance minimization problem and the breaks maximization problem are equivalent when the distance between every pair of teams is equal to 1. We show how to construct schedules with a maximum number of breaks for some tournament types. The connection between breaks maximization and distance minimization is used to derive lower bounds to the mirrored traveling tournament problem and to prove the optimality of solutions found by a heuristic for the latter.