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

``````param maxd integer = 5;
set DEGREES := 0..maxd;
var W {DEGREES} >= 0;  # weight for vertices according to their degrees
var g {DEGREES} >= 0;  # weight for degree reductions from deg i
var h {DEGREES} >= 0;  # weight for degree reductions from deg \le i
var Wmax;              # maximum weight of W[d]

minimize Obj: Wmax;    # minimize the maximum weight

subject to MaxWeight {d in DEGREES}:
Wmax >= W[d];
subject to gNotation {d in DEGREES : 2 <= d}:
g[d] <= W[d]-W[d-1];
subject to hNotation {d in DEGREES, i in DEGREES : 2 <= i <= d}:
h[d] <= W[i]-W[i-1];
subject to Deg3 {p2 in 0..3, p3 in 0..3 : p2+p3=3}:
2^(-W -p2*g -p3*g) + 2^(-W -p2*W -p3*W -h) <=1;
subject to Deg4 {p2 in 0..4, p3 in 0..4, p4 in 0..4 : p2+p3+p4=4}:
2^(-W - p2*g - p3*g - p4*g)
+ 2^(-W - p2*W - p3*W - p4*W - h) <=1;
subject to Deg5 {p2 in 0..5, p3 in 0..5, p4 in 0..5, p5 in 0..5 :
p2+p3+p4+p5=5}:
2^(-W - p2*g - p3*g - p4*g - p5*g)
+ 2^(-W - p2*W - p3*W - p4*W - p5*W - h) <=1;``````

Resource created Monday 08 August 2016, 06:57:47 PM.

file: mis.mod