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 128 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 17 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 170 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 207 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 185 of file atsp.py.

cost

def cost = model.getObjVal()

Definition at line 195 of file atsp.py.

f

f

Definition at line 244 of file atsp.py.

model

def model = mtz(n, c)

Definition at line 192 of file atsp.py.

n

int n = 5

Definition at line 184 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 205 of file atsp.py.

u

u

Definition at line 204 of file atsp.py.

x

x

Definition at line 204 of file atsp.py.