Optimization Online


Constructing a Small Compact Binary Model for the Travelling Salesman Problem

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

Abstract: A variety of formulations for the Travelling Salesman Problem as Mixed Integer Program have been proposed. They contain either non-binary variables or the number of constraints and variables is large. We want to give a new formulation that consists solely of binary variables; the number of variables and the number of constraints are of order $O(n^2 \ln (n)^2)$.

Keywords: Mixed Integer Program, Landau function,Traveling Salesman Problem

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

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

Citation: Institute of Transport Logistics TU Dortmund 07/2015

Download: [PDF]

Entry Submitted: 07/21/2015
Entry Accepted: 07/21/2015
Entry Last Modified: 08/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