atsp Namespace Reference

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

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

Function Documentation

mcf()

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.

References pyscipopt.expr.quicksum().

mtz()

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.

References pyscipopt.expr.quicksum().

mtz_strong()

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.

References pyscipopt.expr.quicksum().

scf()

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.

References pyscipopt.expr.quicksum().

sequence()

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

arcs

list arcs = [(i,j) for (i,j) in x if model.getVal(x[i,j]) > .5]

Definition at line 209 of file atsp.py.

c

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.

cost

def cost = model.getObjVal()

Definition at line 197 of file atsp.py.

f

f

Definition at line 246 of file atsp.py.

model

def model = mtz(n,c)

Definition at line 194 of file atsp.py.

n

int n = 5

Definition at line 186 of file atsp.py.

sol

def sol = [i for (p,i) in sorted([(int(model.getVal(u[i])+.5),i) for i in range(1,n+1)])]

Definition at line 207 of file atsp.py.

u

u

Definition at line 206 of file atsp.py.

x

x

Definition at line 206 of file atsp.py.