set students;
set nodes ordered;
# set of classes in this case
set exams{students} within nodes;
# set of exams for each student
set arcs := {i in nodes, j in nodes:
ord(i) < ord(j) and exists {s in students} ((i in exams[s]) and (j in exams[s]))};
# there is an arc between nodes (classes) i and j
# if there is a student who takes both classes
set colors;
# set of exam times in this case
var use{c in colors} binary;
# is 1 if color c is used, 0 otherwise
var assign{i in nodes, c in colors} binary;
# is 1 if node i has color c, 0 otherwise
minimize number_of_colors: sum{c in colors} use[c];
s.t. one_color_for_each_node{i in nodes}:
sum{c in colors} assign[i,c] = 1;
s.t. different_colors_for_adjacent_nodes
{c in colors, i in nodes, j in nodes: (i,j) in arcs}:
assign[i,c] + assign[j,c] <= 1;
s.t. assign_only_chosen_colors{i in nodes, c in colors}:
assign[i,c] <= use[c];
data;
set colors:= 8am 10am 12pm 2pm 4pm 6pm;
set nodes:= Math English Biology Chemistry Compscience Geography
Psychology Spanish History French;
set students:= 1 2 3 4 5 6 7;
set exams[1]:= Math English Biology Chemistry ;
set exams[2]:= Math English Compscience Geography;
set exams[3]:= Biology Psychology Geography Spanish;
set exams[4]:= Biology Compscience History French;
set exams[5]:= English Psychology Compscience History;
set exams[6]:= Psychology Chemistry Compscience French;
set exams[7]:= Psychology Geography History Spanish;
-----------------------------------------------------------------
computer output
LP_SOLVE 4.0.1.0: optimal, objective 6
46938 simplex iterations
5249 branch & bound nodes: depth 25
: _varname _var :=
1 "use['8am']" 1
2 "use['10am']" 1
3 "use['12pm']" 1
4 "use['2pm']" 1
5 "use['4pm']" 1
6 "use['6pm']" 1
7 "assign['Math','8am']" 0
8 "assign['Math','10am']" 0
9 "assign['Math','12pm']" 0
10 "assign['Math','2pm']" 0
11 "assign['Math','4pm']" 0
12 "assign['Math','6pm']" 1
13 "assign['English','8am']" 0
14 "assign['English','10am']" 0
15 "assign['English','12pm']" 0
16 "assign['English','2pm']" 0
17 "assign['English','4pm']" 1
18 "assign['English','6pm']" 0
19 "assign['Biology','8am']" 0
20 "assign['Biology','10am']" 0
21 "assign['Biology','12pm']" 0
22 "assign['Biology','2pm']" 1
23 "assign['Biology','4pm']" 0
24 "assign['Biology','6pm']" 0
25 "assign['Chemistry','8am']" 0
26 "assign['Chemistry','10am']" 0
27 "assign['Chemistry','12pm']" 1
28 "assign['Chemistry','2pm']" 0
29 "assign['Chemistry','4pm']" 0
30 "assign['Chemistry','6pm']" 0
31 "assign['Compscience','8am']" 0
32 "assign['Compscience','10am']" 1
33 "assign['Compscience','12pm']" 0
34 "assign['Compscience','2pm']" 0
35 "assign['Compscience','4pm']" 0
36 "assign['Compscience','6pm']" 0
37 "assign['Geography','8am']" 0
38 "assign['Geography','10am']" 0
39 "assign['Geography','12pm']" 1
40 "assign['Geography','2pm']" 0
41 "assign['Geography','4pm']" 0
42 "assign['Geography','6pm']" 0
43 "assign['Psychology','8am']" 0
44 "assign['Psychology','10am']" 0
45 "assign['Psychology','12pm']" 0
46 "assign['Psychology','2pm']" 0
47 "assign['Psychology','4pm']" 0
48 "assign['Psychology','6pm']" 1
49 "assign['Spanish','8am']" 0
50 "assign['Spanish','10am']" 0
51 "assign['Spanish','12pm']" 0
52 "assign['Spanish','2pm']" 0
53 "assign['Spanish','4pm']" 1
54 "assign['Spanish','6pm']" 0
55 "assign['History','8am']" 1
56 "assign['History','10am']" 0
57 "assign['History','12pm']" 0
58 "assign['History','2pm']" 0
59 "assign['History','4pm']" 0
60 "assign['History','6pm']" 0
61 "assign['French','8am']" 0
62 "assign['French','10am']" 0
63 "assign['French','12pm']" 0
64 "assign['French','2pm']" 0
65 "assign['French','4pm']" 1
66 "assign['French','6pm']" 0
;
