m2csp.mod

# Max 2CSP
param maxd integer = 5;
set DEGREES := 0..maxd;
var W {DEGREES};  # Weights for vertices according to degree
var We;           # Weights for edges

minimize Obj: We;
# ensure that vertex weights only improve the bound,
# so we may ignore them in the final bound
subject to Vneg {d in DEGREES}:
  W[d] <= 0;
# Nonnegative measure
subject to Nonneg {d in DEGREES}:
  0.5*d*We + W[d] >= 0;

subject to Deg0: # 0-reduction
  -W[0] <= 0;
subject to Red2: # 2-reduction
  -We-W[2] <= 0;
# Branching: in the worst case, all neighbors have equal degree
subject to Branch {d in 3..maxd, d1 in 3..d}:
  1 - W[d] - d*We - d*(W[d1] - W[d1-1]) <= 0;