---
title: "00. Why do these exams clash?"
engine: julia
julia:
exeflags: ["--project=@."]
---
An exam office has ten courses and two time slots. When students are enrolled in
two courses, those exams should be separated. We will build the optimization
problem from that sentence before trying to solve it.
## What information do we actually have?
The course codes are labels; the mathematics does not depend on their names.
```{julia}
#| label: conflict-data
courses = ["LA", "OPT", "STAT", "ML", "NUM",
"CTRL", "PROB", "GRAPH", "DATA", "SIGNAL"]
# (course 1, course 2, number of shared students)
conflicts = [
(1, 2, 20), (1, 5, 10), (1, 6, 15),
(2, 3, 10), (2, 6, 20), (2, 7, 10),
(3, 4, 20), (3, 7, 15), (3, 8, 10),
(4, 5, 10), (4, 8, 20), (4, 9, 15),
(5, 9, 20), (5, 10, 10),
(6, 7, 10), (6, 10, 20),
(7, 8, 20), (7, 10, 15),
(8, 9, 10), (9, 10, 20),
]
[(courses[i], courses[j], shared) for (i, j, shared) in conflicts]
```
This is already a model, with assumptions worth stating. We count only
pairwise clashes, treat every affected student equally, and allow exactly two
slots. A real registrar would also handle room capacity, more time slots,
instructors, and accessibility constraints. Those omissions make this a
teaching problem rather than a deployable scheduler.
## How can a picture preserve the records?
Make one **vertex** for each course. Join two vertices with an **edge** when the
courses share students. Give that edge a **weight** equal to the number of
shared students.
::: {.callout-note title="Go further: graph vocabulary"}
If vertices, weighted edges, and adjacency matrices are new, the relevant
background is only the opening graph definitions—not a full graph-theory
course. MIT OpenCourseWare's
[Mathematics for Computer Science graph notes](https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/pages/readings/)
are a useful optional reference.
:::
We divide the counts by ten to keep the displayed objective small. This changes
its units from students to tens of students; it does not change which schedule
is best.
```{julia}
#| label: build-conflict-matrix
using LinearAlgebra
using LearnSDP
n = length(courses)
W = zeros(n, n)
for (i, j, shared) in conflicts
W[i, j] = W[j, i] = shared / 10
end
@assert W == course_graph()
(symmetric = issymmetric(W), diagonal = diag(W), nonzero_edges = count(!iszero, W) ÷ 2)
```
The symmetric matrix `W` is the graph's weighted adjacency matrix. Entry
`W[i,j]` records the edge weight; a zero means that our data contains no clash
for that pair. Symmetry records that a clash between `LA` and `OPT` is the same
clash viewed in either order.
Now the picture has a provenance:
{fig-alt="A circular graph contains ten labeled course codes. Lines join course pairs that share students, and thicker lines represent more shared students."}
The labels match `courses`; thicker edges have larger weights. The circular
placement is a drawing choice made to keep the picture readable. Distance
around the circle has no meaning.
## When does a schedule avoid a clash?
A two-slot schedule divides the vertices into two groups. In graph language,
that division is a **cut**. An edge crosses the cut when its courses land in
different slots. Its weight then counts toward the conflicts avoided.
Represent slot A by `1` and slot B by `-1`. Here is one proposed schedule:
```{julia}
#| label: score-one-schedule
slot = [1, 1, -1, -1, 1, -1, 1, -1, 1, -1]
slot_A = courses[slot .== 1]
slot_B = courses[slot .== -1]
crossing = [
(courses[i], courses[j], W[i, j])
for i in 1:n for j in (i + 1):n
if W[i, j] > 0 && slot[i] != slot[j]
]
(slot_A, slot_B, crossing, score = sum(last, crossing))
```
The score is `17`, meaning this schedule separates 170 shared-student pairs in
the original units. Edges left inside a slot are the unresolved clashes.
Swapping the names of slots A and B negates every sign but changes no crossing
edge. That symmetry will matter when we count possible schedules.
## What are we trying to maximize?
Our first optimization problem is therefore:
> Divide the courses into two slots to maximize the total weight of edges whose
> endpoints lie in different slots.
This is the **weighted maximum-cut problem**, usually shortened to weighted
Max-Cut. The next chapter will search the small instance exactly and translate
the verbal score into algebra. Semidefinite programming will enter only after
we understand the problem it is relaxing.
## Can you improve the first schedule?
1. Move `LA` to the other slot. Which three edge contributions can change?
2. Construct a schedule with score greater than `17` without using a solver.
3. Explain why storing only the number of courses would be insufficient.
4. Name one real scheduling constraint omitted by this graph model and explain
what can go wrong because of the omission.
