Python code to optimize the analysis of an algorithm for Maximum Independent Set in Lecture 03-branch.

``````from numpy import *
from FuncDesigner import oovar, oovars
from openopt import NLP # install from openopt.org

W = oovars(6)('W')
g = +[W[i]-W[i-1] for i in range(1,6)]
h = oovars(6)('h')
Wmax = oovar('Wmax')

obj = Wmax
startPoint = {W:[1 for i in range(6)],
h:[0 for i in range(6)],
Wmax:1}
q = NLP(obj, startPoint)

for d in range(6): # positive vars
q.constraints.append(W[d] >= 0)
for d in range(6): # Max Weight
q.constraints.append(Wmax >= W[d])
for d in range(2,6): # h notation
for i in range(2,d+1):
q.constraints.append(h[d] <= W[i]-W[i-1])
p = [0 for x in range(6)]
for p in range(4): # Deg 3
p = 3-p
q.constraints.append(  2**(-W-sum([p[i]*g[i] for i in range(2,4)]))
+ 2**(-W-sum([p[i]*W[i] for i in range(2,4)])-h)
<=1)
for p in range(5): # Deg 4
for p in range(5-p):
p = 4-sum(p[2:4])
q.constraints.append(  2**(-W-sum([p[i]*g[i] for i in range(2,5)]))
+ 2**(-W-sum([p[i]*W[i] for i in range(2,5)])-h)
<=1)
for p in range(6): # Deg 5
for p in range(6-p):
for p in range(6-sum(p[2:4])):
p = 5-sum(p[2:5])
q.constraints.append(  2**(-W-sum([p[i]*g[i] for i in range(2,6)]))
+ 2**(-W-sum([p[i]*W[i] for i in range(2,6)])-h)
<=1)
q.ftol = 1e-10
q.xtol = 1e-10
r = q.solve('ralg') # use pyipopt for better performance
Wmax_opt = r(Wmax)
print(r.xf)
print("Running time: {0}^n".format(2**Wmax_opt))
``````

Resource created Monday 08 August 2016, 06:58:39 PM.

file: mis.py