Optimization Online


Solving the Probabilistic Traveling Salesman Problem by Linearising a Quadratic Approximation

J. Fabian Meier(meier***at***itl.tu-dortmund.de)
Uwe Clausen(clausen***at***itl.tu-dortmund.de)

Abstract: The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The resulting Mixed Integer Program is difficult, because the objective function is a high-degree polynomial in the binary edge variables. Linearisations lead to a large number of variables. We show that for large p, the model can be well approximated by a quadratic model. This quadratic model can be linearised to a small linear model which leads to good primal solutions and strong lower bounds up to 80 probabilistic nodes. We explain the approach and present numerical results.

Keywords: Quadratic Optimisation; Linearisation; Quadratic Traveling Salesman Problem

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Integer Programming

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Institute of Transport Logistics TU Dortmund June 2015

Download: [PDF]

Entry Submitted: 06/08/2015
Entry Accepted: 06/08/2015
Entry Last Modified: 06/08/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society