Skip to content

Instantly share code, notes, and snippets.

@mdonoughe

mdonoughe/fastcalls.txt

Created April 4, 2011 19:20
Show Gist options
  • Save mdonoughe/902231 to your computer and use it in GitHub Desktop.
Save mdonoughe/902231 to your computer and use it in GitHub Desktop.
Download ZIP
static routing and wavelength assignment that crashes
Raw
fastcalls.txt
Tue Apr 5 21:56:50 2011 fastdata
930450 function calls (897978 primitive calls) in 2.469 CPU seconds
Ordered by: cumulative time
List reduced from 1350 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.004 0.004 2.473 2.473 {execfile}
1 0.030 0.030 2.469 2.469 solve.py:5(<module>)
1 0.000 0.000 1.926 1.926 baseProblem.py:190(<lambda>)
1 0.000 0.000 1.926 1.926 baseProblem.py:731(minimize)
1 0.000 0.000 1.926 1.926 runProbSolver.py:41(runProbSolver)
1 0.001 0.001 1.725 1.725 MILP.py:19(_Prepare)
1 0.000 0.000 1.724 1.724 LP.py:21(_Prepare)
1 0.001 0.001 1.724 1.724 baseProblem.py:557(_Prepare)
1 0.048 0.048 1.722 1.722 baseProblem.py:279(_prepare)
1171 0.019 0.000 0.988 0.001 ooFun.py:752(D)
4891/2041 0.119 0.000 0.906 0.000 ooFun.py:807(_D)
4891 0.075 0.000 0.604 0.000 ooFun.py:952(_getDerivativeSelf)
1080 0.003 0.000 0.551 0.001 ooFun.py:240(<lambda>)
450 0.070 0.000 0.539 0.001 overloads.py:255(_D)
14372/6962 0.095 0.000 0.358 0.000 ooFun.py:587(_getInput)
9601/2611 0.120 0.000 0.342 0.000 ooFun.py:687(_getFuncCalcEngine)
11886 0.127 0.000 0.307 0.000 fromnumeric.py:32(_wrapit)
2251 0.004 0.000 0.282 0.000 ooFun.py:748(<lambda>)
2251 0.014 0.000 0.278 0.000 ooFun.py:647(_getFunc)
300/270 0.004 0.000 0.276 0.001 ooFun.py:251(<lambda>)
Raw
fastoutput.txt
~/Documents/School/cis590/ILP Homework 2 ‹master*› $ time arch -i386 python2.6 -m cProfile -o fastdata solve.py
physical connections:
[0, 1, 0, 1, 1, 0]
[1, 0, 1, 0, 1, 0]
[0, 1, 0, 0, 1, 1]
[1, 0, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1]
[0, 0, 1, 0, 1, 0]
demand:
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
931
OpenOpt is converting 1170 constraints and 1 variables...
FuncDesigner warning: Probably scipy installation could speed up running the code involved
OpenOpt Warning: Probably scipy installation could speed up running the code involved
--------------------------------------------------
solver: cplex problem: unnamed type: MILP goal: minimum
iter objFunVal
0 0.000e+00
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
1 1.000e+00
istop: 1000 (Cplex status: "integer optimal solution"; exit code: 101)
Solver: Time Elapsed = 0.16 CPU Time Elapsed = 0.161268
objFunValue: 1 (feasible, MaxResidual = 0)
writing graph to graph.dot...
Run graph.dot through GraphViz for visual results.
Ex: neato -Teps -o graph.eps graph.dot
arch -i386 python2.6 -m cProfile -o fastdata solve.py 2.43s user 0.15s system 98% cpu 2.617 total
Raw
myooutil.py
from FuncDesigner import oofun
def print_matrix(mat):
print('\n'.join(map(lambda r: '[%s]' % (', '.join(map(lambda c: str(c), r))), mat)))
def make_matrix(fun, *sizes):
def _mm(fun, ix, sizes):
if len(sizes) > 0:
return map(lambda i: _mm(fun, ix + [i], sizes[1::1]), range(sizes[0]))
return fun(*ix)
return _mm(fun, [], sizes)
def make_network(size, *connections):
net = make_matrix(lambda i, j: 0, size, size)
connect_network(net, *connections)
return net
def connect_network(network, *connections):
for c in connections:
network[c[0]][c[1]] += 1
# i is the number of dimensions in the input data that we want to flatten
# i = 1 means to flatten once to make a 1D matrix from a 2D matrix
def flatten_matrix(mat, i = -1):
if isinstance(mat, list) and not isinstance(mat, oovar) and i != 0:
return reduce(lambda a, b: a + flatten_matrix(b, i - 1), mat, [])
return mat
# remove all traces of openopt from a matrix
# extracts the values of variables
def clean_matrix(mat, problem):
if isinstance(mat, oofun):
return mat(problem)
elif isinstance(mat, list):
return [clean_matrix(m, problem) for m in mat]
else:
return mat
Raw
slowcalls.txt
Tue Apr 5 21:52:17 2011 slowdata
13198475 function calls (13180703 primitive calls) in 14.598 CPU seconds
Ordered by: cumulative time
List reduced from 1347 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.004 0.004 14.601 14.601 {execfile}
1 0.029 0.029 14.598 14.598 solve.py:5(<module>)
1 0.000 0.000 14.151 14.151 baseProblem.py:190(<lambda>)
1 0.000 0.000 14.151 14.151 baseProblem.py:731(minimize)
1 0.000 0.000 14.151 14.151 runProbSolver.py:41(runProbSolver)
1 0.014 0.014 13.994 13.994 MILP.py:19(_Prepare)
1 0.000 0.000 13.851 13.851 LP.py:21(_Prepare)
1 0.001 0.001 13.836 13.836 baseProblem.py:557(_Prepare)
1 0.114 0.114 13.835 13.835 baseProblem.py:279(_prepare)
8341 5.201 0.001 6.738 0.001 ooFun.py:1098(getOrder)
900 0.039 0.000 5.947 0.007 overloads.py:239(getOrder)
543 1.146 0.002 5.895 0.011 ooPoint.py:17(__init__)
540/420 0.004 0.000 4.577 0.011 ooFun.py:214(<lambda>)
271 0.233 0.001 3.617 0.013 ooFun.py:752(D)
503671 0.328 0.000 3.302 0.000 ooPoint.py:21(<lambda>)
1351 0.065 0.000 3.104 0.002 ooFun.py:748(<lambda>)
510551 0.948 0.000 3.040 0.000 type_check.py:73(asfarray)
1351 0.014 0.000 3.039 0.002 ooFun.py:647(_getFunc)
8604266 1.683 0.000 1.683 0.000 ooFun.py:150(<lambda>)
524161 1.477 0.000 1.477 0.000 numeric.py:216(asarray)
Raw
slowoutput.txt
~/Documents/School/cis590/ILP Homework 2 ‹master*› $ time arch -i386 python2.6 -m cProfile -o slowdata solve.py
physical connections:
[0, 1, 0, 1, 1, 0]
[1, 0, 1, 0, 1, 0]
[0, 1, 0, 0, 1, 1]
[1, 0, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1]
[0, 0, 1, 0, 1, 0]
demand:
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
931
OpenOpt is converting 1170 constraints and 931 variables...
OpenOpt Warning: Probably scipy installation could speed up running the code involved
--------------------------------------------------
solver: cplex problem: unnamed type: MILP goal: minimum
iter objFunVal
0 0.000e+00
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
1 1.000e+00
istop: 1000 (Cplex status: "integer optimal solution"; exit code: 101)
Solver: Time Elapsed = 0.12 CPU Time Elapsed = 0.116161
objFunValue: 1 (feasible, MaxResidual = 0)
writing graph to graph.dot...
Run graph.dot through GraphViz for visual results.
Ex: neato -Teps -o graph.eps graph.dot
arch -i386 python2.6 -m cProfile -o slowdata solve.py 14.53s user 0.16s system 99% cpu 14.738 total
Raw
solve.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Matthew Donoughe
from FuncDesigner import *
from openopt import MILP
from myooutil import *
import copy
import numpy
# network size, in nodes
NET_SIZE = 6
# number of wavelengths per link
WAVELENGTHS = 1
# 0 -- 1 -- 2
# | \ | / |
# | \ | / |
# 3 -- 4 -- 5
# create the physical network matrix
# multiple links from s to d are allowed
# asymetric networks are allowed
# the diagonal is ignored
physical = [
[0, 1, 0, 1, 1, 0], # 0 to d
[1, 0, 1, 0, 1, 0], # 1 to d
[0, 1, 0, 0, 1, 1], # 2 to d
[1, 0, 0, 0, 1, 0], # 3 to d
[1, 1, 1, 1, 0, 1], # 4 to d
[0, 0, 1, 0, 1, 0] # 5 to d
]
print('physical connections:')
print_matrix(physical)
# create the demand network matrix
# multiple requests from s to d are allowed
# asymmetric networks are allowed
# the diagonal is ignored(nodes are assumed to have an internal self-connection)
demand = [
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
]
# it is also possible to define the demand matrix like this:
#demand = make_network(NET_SIZE, (0, 5), (0, 5), (0, 5), (5, 0), (0, 3), (0, 3), (2, 4), (4, 2), (0, 4), (0, 4), (4, 0))
print('demand:')
print_matrix(demand)
constraints = []
# allocate space for all variables in a single vector
# flow_max is one element
# connection_wavelengths is NET_SIZE ** 2 * WAVELENGTHS logical elements
# NETSIZE places where WAVELENGTHS positions have the same s and d
# links is NET_SIZE ** 4 * WAVELENGTHS logical elements
# NET_SIZE places where NET_SIZE ** 2 * WAVELENGTHS positions have the same s and d
# NET_SIZE ** 2 * WAVELENGTHS places where NETSIZE positions have the same i and j
# NET_SIZE ** 2 * WAVELENGTHS places where 1 position has the same s d i j(and was subtracted twice)
oodata = oovar(size = NET_SIZE ** 4 * WAVELENGTHS - 2 * NET_SIZE ** 3 * WAVELENGTHS + 2 * NET_SIZE ** 2 * WAVELENGTHS - NET_SIZE * WAVELENGTHS + 1)
#oodata = [oovar('oodata[%d]' % i) for i in xrange(NET_SIZE ** 4 * WAVELENGTHS - 2 * NET_SIZE ** 3 * WAVELENGTHS + 2 * NET_SIZE ** 2 * WAVELENGTHS - NET_SIZE * WAVELENGTHS + 1)]
data_index = 0
# assign wavelengnths to connections
connection_wavelengths = make_matrix(lambda s, d, w: 0, NET_SIZE, NET_SIZE, WAVELENGTHS)
# strip out self connections
for s in range(NET_SIZE):
connection_wavelengths[s][s] = []
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
connection_wavelengths[s][d][w] = oodata[data_index]
data_index += 1
# assign connections to physical links
links = make_matrix(lambda s, d, w, i, j: 0, NET_SIZE, NET_SIZE, WAVELENGTHS, NET_SIZE, NET_SIZE)
# strip out self connections
for s in range(NET_SIZE):
links[s][s] = make_matrix(lambda w, i: [], WAVELENGTHS, NET_SIZE)
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
for i in range(NET_SIZE):
links[s][d][w][i][i] = 0
for j in range(NET_SIZE):
if i != j:
links[s][d][w][i][j] = oodata[data_index]
data_index += 1
# 1
flow_max = oodata[data_index]
data_index += 1
print(data_index)
# 2
# Fmax ≥ total number of flows in the same direction on any link
temp = make_matrix(lambda i, j: [], NET_SIZE, NET_SIZE)
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
for i in range(NET_SIZE):
for j in range(NET_SIZE):
if i != j:
temp[i][j] += [links[s][d][w][i][j]]
for i in range(NET_SIZE):
for j in range(NET_SIZE):
if i != j:
constraints += [(flow_max >= sum(temp[i][j]))('Fmax >= flows on %d->%d' % (i, j))]
del temp
# 3
# the difference between inbound and outbound must be the number of connections added/removed to/from the network at that node
inbound = make_matrix(lambda s, d, w, j: [], NET_SIZE, NET_SIZE, WAVELENGTHS, NET_SIZE)
outbound = make_matrix(lambda s, d, w, i: [], NET_SIZE, NET_SIZE, WAVELENGTHS, NET_SIZE)
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
for i in range(NET_SIZE):
for j in range(NET_SIZE):
if i != j:
inbound[s][d][w][j] += [links[s][d][w][i][j]]
outbound[s][d][w][i] += [links[s][d][w][i][j]]
inbound = [[[[sum(j) for j in w] for w in d] for d in s] for s in inbound]
outbound = [[[[sum(i) for i in w] for w in d] for d in s] for s in outbound]
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
for j in range(NET_SIZE):
diff = (inbound[s][d][w][j] - outbound[s][d][w][j])('diff[s=%d,d=%d,w=%d,j=%d]' % (s, d, w, j))
if s == j:
constraints += [(diff == -connection_wavelengths[s][d][w])('%s == -%s' % (diff, connection_wavelengths[s][d][w]))]
elif d == j:
constraints += [(diff == connection_wavelengths[s][d][w])('%s == %s' % (diff, connection_wavelengths[s][d][w]))]
else:
constraints += [(diff == 0)('%s == 0' % diff)]
del inbound
del outbound
# 4
# wavelengths used between s and d must equal the demand for connections
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
constraints += [(sum(connection_wavelengths[s][d]) == demand[s][d])('connections %d->%d == demand' % (s, d))]
# 5
# connections from i to j on wavelength w must not be negative
# in the homework formulation, this also says that the number must be <= 1,
# but a) this is already taken care of by ensuring only one lightpath per wavelength per link,
# and b) this is incorrect if there are multiple physical links(then there could be more)
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
for i in range(NET_SIZE):
for j in range(NET_SIZE):
if i != j:
constraints += [(links[s][d][w][i][j] >= 0)('%s >= 0' % links[s][d][w][i][j])]
# 6
# number of lightpaths on a given wavelength may not exceed the number of links
# this differs from the homework formulation in two ways:
# 1) it prevents lightpaths over links that do not exist
# 2) it allows for multiple physical links
temp = make_matrix(lambda i, j, w: [], NET_SIZE, NET_SIZE, WAVELENGTHS)
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
for i in range(NET_SIZE):
for j in range(NET_SIZE):
if i != j:
temp[i][j][w] += [links[s][d][w][i][j]]
for i in range(NET_SIZE):
for j in range(NET_SIZE):
if i != j:
for w in range(WAVELENGTHS):
constraints += [(sum(temp[i][j][w]) <= physical[i][j])('lightpaths[i=%d,j=%d,w=%d] <= physical[i=%d,j=%d]' % (i, j, w, i, j))]
del temp
# start with all variables set to 0
startPoint = {oodata: numpy.zeros(data_index)}
#startPoint = dict([(v, 0) for v in oodata])
print('OpenOpt is converting %d constraints and %d variables...' % (len(constraints), len(startPoint)))
problem = MILP(flow_max, startPoint, constraints = constraints, intVars = [oodata])
#problem = MILP(flow_max, startPoint, constraints = constraints, intVars = oodata)
# cplex requires:
# OpenOpt 0.33
# CPLEX 12
# the Python API distributed with CPLEX must be installed(on Mac OS X x86_64, you must run 'arch -i386 python2.6 solve.py' or it won't work)
# the CPLEX license must be installed properly
result = problem.minimize('cplex')
# glpk requires:
# OpenOpt
# CVXOPT
# glpk
#result = problem.minimize('glpk')
# extract the results from OpenOpt
links = clean_matrix(links, result)
# convert the results to integers
links = [[[[[int(j) for j in i] for i in w] for w in d] for d in s] for s in links]
# graph the result
print('writing graph to graph.dot...')
# make copies so we can better draw bidirectional links without side effects
phys = copy.deepcopy(physical)
lnks = copy.deepcopy(links)
with open('graph.dot', 'w') as g:
g.write('digraph {\n')
g.write('edge [colorscheme=set19,decorate=true,fontsize=6];\n')
g.write('n0 [pos="0,3",pin=true];\n')
g.write('n1 [pos="3,3",pin=true];\n')
g.write('n2 [pos="6,3",pin=true];\n')
g.write('n3 [pos="0,0",pin=true];\n')
g.write('n4 [pos="3,0",pin=true];\n')
g.write('n5 [pos="6,0",pin=true];\n')
# draw physical links
g.write('// physical links\n')
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for i in range(phys[s][d]):
if phys[d][s] > 0:
g.write('n%d -> n%d [dir=none];\n' % (s, d))
phys[d][s] -= 1
else:
g.write('n%d -> n%d;\n' % (s, d))
g.write('// solution lightpaths\n')
# draw lightpaths
for s in range(NET_SIZE):
for d in range(NET_SIZE):
if s != d:
for w in range(WAVELENGTHS):
for i in range(NET_SIZE):
for j in range(NET_SIZE):
if i != j:
for v in range(lnks[s][d][w][i][j]):
if lnks[d][s][w][j][i] > 0:
g.write('n%d -> n%d [color=%d,label="n%d--n%d",dir=both];\n' % (i, j, w + 1, s, d))
lnks[d][s][w][j][i] -= 1
else:
g.write('n%d -> n%d [color=%d,label="n%d->n%d"];\n' % (i, j, w + 1, s, d))
g.write('}\n')
print('Run graph.dot through GraphViz for visual results.')
print('Ex: neato -Teps -o graph.eps graph.dot')
@akamax
Copy link

akamax commented May 28, 2016

can i implement this in gurobi?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment