atsp.py File Reference

solve the asymmetric traveling salesman problem More...

Go to the source code of this file.

Functions
def	mtz (n, c)
def	mtz_strong (n, c)
def	scf (n, c)
def	mcf (n, c)
def	sequence (arcs)

Variables
int	n = 5
dictionary	c
	model = mtz(n,c)
	cost = model.getObjVal()
	x
	u
list	sol = [i for (p,i) in sorted([(int(model.getVal(u[i])+.5),i) for i in range(1,n+1)])]
list	arcs = [(i,j) for (i,j) in x if model.getVal(x[i,j]) > .5]
	f

Detailed Description

solve the asymmetric traveling salesman problem

Definition in file atsp.py.

Function Documentation

def atsp.mcf	(		n,
			c
	)

mcf: multi-commodity flow formulation for the (asymmetric) traveling salesman problem
Parameters:
    - n: number of nodes
    - c[i,j]: cost for traversing arc (i,j)
Returns a model, ready to be solved.

Definition at line 129 of file atsp.py.

def atsp.mtz	(		n,
			c
	)

mtz: Miller-Tucker-Zemlin's model for the (asymmetric) traveling salesman problem
(potential formulation)
Parameters:
    - n: number of nodes
    - c[i,j]: cost for traversing arc (i,j)
Returns a model, ready to be solved.

Definition at line 16 of file atsp.py.

def atsp.mtz_strong	(		n,
			c
	)

mtz_strong: Miller-Tucker-Zemlin's model for the (asymmetric) traveling salesman problem
(potential formulation, adding stronger constraints)
Parameters:
    n - number of nodes
    c[i,j] - cost for traversing arc (i,j)
Returns a model, ready to be solved.

Definition at line 50 of file atsp.py.

def atsp.scf	(		n,
			c
	)

scf: single-commodity flow formulation for the (asymmetric) traveling salesman problem
Parameters:
    - n: number of nodes
    - c[i,j]: cost for traversing arc (i,j)
Returns a model, ready to be solved.

Definition at line 87 of file atsp.py.

def atsp.sequence

(

arcs

)

sequence: make a list of cities to visit, from set of arcs

Definition at line 172 of file atsp.py.

Variable Documentation

dictionary c

Initial value:

= { (1,1):0,  (1,2):1989,  (1,3):102, (1,4):102, (1,5):103,
          (2,1):104, (2,2):0,  (2,3):11,  (2,4):104, (2,5):108,
          (3,1):107, (3,2):108, (3,3):0,  (3,4):19,  (3,5):102,
          (4,1):109, (4,2):102, (4,3):107, (4,4):0,  (4,5):15,
          (5,1):13,  (5,2):103, (5,3):104, (5,4):101, (5,5):0,
         }

Definition at line 187 of file atsp.py.