set V ordered; # nodes
# for the Conflict constraints of this model, we need to have an ordering on V.
set E within V cross V; # edges, defined for u < v only (according to the vertex ordering)
check{(u,v) in E)}: ord(u) < ord(v);
# check that the declaration of E in the data file respects the ordering.
var x {V} binary;
# describes whether a vertex belongs to the clique.
param w {V} default 1;
# if no weights are specified, we consider the problem of finding
# a stable set of maximum size.
maximize TotalWeight:
sum {v in V} x[v]*w[v];
# each pair of clique vertices has to be connected by an edge.
# This is equivalent to saying that there is no 'non-edge' between clique vertices,
# which can be implemented similarly to the conflict condition of the stable set problem.
# One has to be careful when defining the set of non-deges, as has been demonstrated in the lecture.
s.t. Conflicts {u in V, v in V: (u,v) in (V cross V) diff E
and v<>u and ord(u) < ord(v)}:
x[u] + x[v] <= 1;