01. Can we try every schedule?

Chapter 00 turned enrollment overlaps into a weighted graph and a schedule into a cut. We can now ask a computational question: among all two-slot schedules, which cut has the greatest weight?

How many schedules are really different?

Each of ten courses has two slot choices, giving $2^{10}=1024$ labeled timetables. Every timetable has a mirror image obtained by swapping the names of slots A and B. A timetable and its mirror separate exactly the same course pairs, so the 1024 possibilities form 512 equivalent pairs. There are therefore $1024/2=512$ distinct cuts.

For 60 courses, the same count is $2^{59}$—more than five hundred quadrillion. The ten-node drawing is our inspectable teaching instance; 60 describes where this exact strategy stops being plausible. They are not the same graph.

Can one formula score every schedule?

Let $s_i\in\{-1,1\}$ record the slot assigned to course $i$: 1 for A and -1 for B. For one pair of courses,

\[ \frac{1-s_i s_j}{2} = \begin{cases} 0, & s_i=s_j,\\ 1, & s_i\ne s_j. \end{cases} \]

Our objective is the total conflict weight the schedule avoids. A separated pair contributes its full weight $W_{ij}$ to that total, so its indicator must be 1. A pair left in the same slot has not been avoided, so it contributes 0. This does not make an unresolved clash unimportant; it means that clash adds nothing to the avoided total. Because the total weight of all edges is fixed, maximizing avoided weight is equivalent to minimizing unresolved weight. Max-Cut uses the first convention.

Adding the weighted indicator over every course pair gives the cut weight and the optimization problem in one expression:

\[ \begin{aligned} \operatorname{cut}(s) &=\sum_{i<j}W_{ij}\frac{1-s_i s_j}{2},\\ \text{maximize}\quad &\operatorname{cut}(s) \quad\text{over }s\in\{-1,1\}^{10}. \end{aligned} \]

The condition $i<j$ makes the sum visit each undirected edge once. Before running the code, predict whether it reproduces the score computed edge by edge in Chapter 00.

using LearnSDP

W = course_graph()
candidate = [1, 1, -1, -1, 1, -1, 1, -1, 1, -1]

direct_score = sum(
    W[i, j] * (1 - candidate[i] * candidate[j]) / 2
    for i in axes(W, 1) for j in (i + 1):size(W, 2)
)

(direct_score, helper_score = cut_weight(W, candidate))

(direct_score = 17.0, helper_score = 17.0)

The agreement checks our formula against the edge-by-edge score from Chapter 00. Can the same formula inspect every possible timetable?

Can brute force settle this instance?

For ten courses, a direct loop is enough:

function enumerate_cuts(W)
    n = size(W, 1)
    best_score = -Inf
    best_signs = ones(Int, n)
    scores = Float64[]

    # Checking all labeled timetables is simpler; each cut appears twice.
    for mask in 0:(2^n - 1)
        signs = ones(Int, n)
        for j in 1:n
            signs[j] = ((mask >> (j - 1)) & 1) == 1 ? -1 : 1
        end
        score = cut_weight(W, signs)
        push!(scores, score)
        if score > best_score
            best_score, best_signs = score, copy(signs)
        end
    end
    return (; best_score, best_signs, scores)
end

exact = enumerate_cuts(W)
(score = exact.best_score,
 slot_A = findall(==(1), exact.best_signs),
 slot_B = findall(==(-1), exact.best_signs),
 labeled_timetables_checked = length(exact.scores),
 distinct_cuts = length(exact.scores) ÷ 2)

(score = 23.0, slot_A = [2, 3, 5, 8, 10], slot_B = [1, 4, 6, 7, 9], labeled_timetables_checked = 1024, distinct_cuts = 512)

The optimum is 23, or 230 separated shared-student pairs in the original units. The loop evaluates all 1,024 labeled timetables, so every distinct cut appears twice. That duplication is harmless at this scale. The search establishes the optimum because every labeled timetable is evaluated.

Why rewrite the score with a matrix?

Trying every timetable works for ten courses, but adding one course doubles the search. We want another route. The score depends only on whether each pair of courses has the same sign or different signs, so we will record all of those pairwise relationships in a matrix. This will let us keep the same scoring rule while later allowing a broader set of relationship tables than exact timetables can produce.

Start with the cut formula we already have:

\[ \operatorname{cut}(s) =\frac12\sum_{i<j}W_{ij}(1-s_i s_j). \]

So far, $s_i$ has meant the sign assigned to course $i$. Write all ten signs as one column vector:

\[ s= \begin{bmatrix} s_1\\ \vdots\\ s_{10} \end{bmatrix}, \qquad s_i\in\{-1,1\}. \]

Now define $d_i$ as the total conflict weight touching course $i$:

\[ d_i=\sum_j W_{ij}. \]

The symbol $d$ means the column vector containing those ten totals, and $D$ means the diagonal matrix made from that vector:

\[ d= \begin{bmatrix} d_1\\ \vdots\\ d_{10} \end{bmatrix}, \qquad D=\operatorname{Diag}(d_1,\ldots,d_{10}). \]

Finally, define

\[ L=D-W. \]

Why does this matrix reproduce the cut score? Expand the matrix products one step at a time:

\[ \begin{aligned} s^T Ls &=s^T(D-W)s \\ &=s^TDs-s^TWs \\ &=\sum_i d_i s_i^2-\sum_{i,j}W_{ij}s_i s_j. \end{aligned} \]

Every $s_i$ is either $-1$ or $1$, so $s_i^2=1$. Also, $d_i=\sum_jW_{ij}$. Therefore,

\[ \begin{aligned} s^T Ls &=\sum_{i,j}W_{ij}-\sum_{i,j}W_{ij}s_i s_j \\ &=\sum_{i,j}W_{ij}(1-s_i s_j) \\ &=2\sum_{i<j}W_{ij}(1-s_i s_j) \\ &=4\operatorname{cut}(s). \end{aligned} \]

The factor $2$ in the third line appears because the sum over all $(i,j)$ counts each undirected conflict edge once as $(i,j)$ and again as $(j,i)$. We have now derived

\[ \operatorname{cut}(s)=\frac14s^TLs. \]

The matrix $L=D-W$ is called the weighted graph Laplacian. Here, its name matters less than the calculation: the displayed expansion shows exactly how it gives the score we started with.

We still have products such as $s_i s_j$. Give the complete table of those products a name:

\[ X=ss^T= \begin{bmatrix} s_1s_1 & \cdots & s_1s_{10}\\ \vdots & \ddots & \vdots\\ s_{10}s_1 & \cdots & s_{10}s_{10} \end{bmatrix}. \]

Uppercase $X$ denotes a matrix, and its entry in row $i$, column $j$ is

\[ X_{ij}=s_i s_j. \]

Thus $X_{ij}=1$ when courses $i$ and $j$ use the same slot, and $X_{ij}=-1$ when they use different slots. Every diagonal entry is $X_{ii}=s_i^2=1$. The matrix $X$ is simply a table of the pairwise slot relationships that the score uses.

Expand the quadratic form once more:

\[ s^TLs =\sum_{i,j}L_{ij}s_i s_j =\sum_{i,j}L_{ij}X_{ij}. \]

The last sum is abbreviated by $\langle L,X\rangle$: multiply corresponding entries of $L$ and $X$, then add the results. Hence

\[ \operatorname{cut}(s)=\frac14\langle L,X\rangle. \]

Nothing in this identity has shortened the exact search. To find the best timetable with it, we could still take each of the 1,024 sign vectors, build its matrix $X$, and evaluate the score. We would have changed the calculation, but not the amount of searching.

The matrix does reveal a new question: which pairwise-relationship tables can actually come from a two-slot timetable?

For example, the three-course timetable

\[ s= \begin{bmatrix} 1\\ 1\\ -1 \end{bmatrix} \]

produces

\[ X=ss^T= \begin{bmatrix} 1 & 1 & -1\\ 1 & 1 & -1\\ -1 & -1 & 1 \end{bmatrix}. \]

Courses 1 and 2 share a slot, and course 3 occupies the other slot. Now consider a different table:

\[ Y= \begin{bmatrix} 1 & -1 & -1\\ -1 & 1 & -1\\ -1 & -1 & 1 \end{bmatrix}. \]

It claims that every pair of courses occupies different slots. No two-slot timetable can do that for three courses. So a symmetric table with $1$ on its diagonal and $\pm1$ elsewhere is not automatically a valid timetable table. The pairwise claims must agree with one another.

A matrix made as $X=ss^T$ is guaranteed to be consistent. For any three courses,

\[ X_{ij}X_{jk} =(s_i s_j)(s_j s_k) =s_i s_k =X_{ik}, \]

because $s_j^2=1$. The impossible table $Y$ fails this check: it says courses 1 and 2 differ and courses 2 and 3 differ, which should force courses 1 and 3 to match, yet it says they differ too.

using LinearAlgebra

signs = exact.best_signs
incident_weights = W * ones(size(W, 1))
degree_matrix = Diagonal(incident_weights)
laplacian = degree_matrix - W
pairwise_products = signs * signs'

direct = cut_weight(W, signs)
quadratic = dot(signs, laplacian * signs) / 4
matrix_form = sum(laplacian .* pairwise_products) / 4

@assert direct ≈ quadratic ≈ matrix_form
(direct, quadratic, matrix_form,
 diagonal = diag(pairwise_products),
 entries = sort(unique(pairwise_products)))

(direct = 23.0, quadratic = 23.0, matrix_form = 23.0, diagonal = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], entries = [-1, 1])

Why keep the matrix form if it does not yet reduce the search? The signs describe one timetable; $X$ exposes all of its pairwise relationships at once. Those products can also be read as inner products, which gives them a geometric meaning. Chapter 02 develops that geometry and asks how a matrix can store relationships among vectors. Only after that foundation will we change which matrices are allowed.

Try it yourself

Complete learner/01_searching_for_a_cut.jl without calling exact_maxcut.
Verify the quadratic identity for five randomly generated sign vectors.
Add an eleventh course with one conflict edge. Predict how many distinct schedules enumeration will inspect.
Explain the difference between “the best schedule found” and “the best schedule,” and why enumeration closes that gap here.

--- title: "01. Can we try every schedule?" engine: julia julia: exeflags: ["--project=@."] --- Chapter 00 turned enrollment overlaps into a weighted graph and a schedule into a cut. We can now ask a computational question: among all two-slot schedules, which cut has the greatest weight? ## How many schedules are really different? Each of ten courses has two slot choices, giving $2^{10}=1024$ labeled timetables. Every timetable has a mirror image obtained by swapping the names of slots A and B. A timetable and its mirror separate exactly the same course pairs, so the 1024 possibilities form 512 equivalent pairs. There are therefore $1024/2=512$ distinct cuts. For 60 courses, the same count is $2^{59}$—more than five hundred quadrillion. The ten-node drawing is our inspectable teaching instance; 60 describes where this exact strategy stops being plausible. They are not the same graph. ## Can one formula score every schedule? Let $s_i\in\{-1,1\}$ record the slot assigned to course $i$: `1` for A and `-1` for B. For one pair of courses, $$ \frac{1-s_i s_j}{2} = \begin{cases} 0, & s_i=s_j,\\ 1, & s_i\ne s_j. \end{cases} $$ Our objective is the total conflict weight the schedule **avoids**. A separated pair contributes its full weight $W_{ij}$ to that total, so its indicator must be `1`. A pair left in the same slot has not been avoided, so it contributes `0`. This does not make an unresolved clash unimportant; it means that clash adds nothing to the avoided total. Because the total weight of all edges is fixed, maximizing avoided weight is equivalent to minimizing unresolved weight. Max-Cut uses the first convention. Adding the weighted indicator over every course pair gives the cut weight and the optimization problem in one expression: $$ \begin{aligned} \operatorname{cut}(s) &=\sum_{i<j}W_{ij}\frac{1-s_i s_j}{2},\\ \text{maximize}\quad &\operatorname{cut}(s) \quad\text{over }s\in\{-1,1\}^{10}. \end{aligned} $$ The condition $i<j$ makes the sum visit each undirected edge once. Before running the code, predict whether it reproduces the score computed edge by edge in Chapter 00. ```{julia} #| label: direct-cut-score using LearnSDP W = course_graph() candidate = [1, 1, -1, -1, 1, -1, 1, -1, 1, -1] direct_score = sum( W[i, j] * (1 - candidate[i] * candidate[j]) / 2 for i in axes(W, 1) for j in (i + 1):size(W, 2) ) (direct_score, helper_score = cut_weight(W, candidate)) ``` The agreement checks our formula against the edge-by-edge score from Chapter 00. Can the same formula inspect every possible timetable? ## Can brute force settle this instance? For ten courses, a direct loop is enough: ```{julia} #| label: enumerate-schedules function enumerate_cuts(W) n = size(W, 1) best_score = -Inf best_signs = ones(Int, n) scores = Float64[] # Checking all labeled timetables is simpler; each cut appears twice. for mask in 0:(2^n - 1) signs = ones(Int, n) for j in 1:n signs[j] = ((mask >> (j - 1)) & 1) == 1 ? -1 : 1 end score = cut_weight(W, signs) push!(scores, score) if score > best_score best_score, best_signs = score, copy(signs) end end return (; best_score, best_signs, scores) end exact = enumerate_cuts(W) (score = exact.best_score, slot_A = findall(==(1), exact.best_signs), slot_B = findall(==(-1), exact.best_signs), labeled_timetables_checked = length(exact.scores), distinct_cuts = length(exact.scores) ÷ 2) ``` The optimum is `23`, or 230 separated shared-student pairs in the original units. The loop evaluates all 1,024 labeled timetables, so every distinct cut appears twice. That duplication is harmless at this scale. The search establishes the optimum because every labeled timetable is evaluated. ## Why rewrite the score with a matrix? Trying every timetable works for ten courses, but adding one course doubles the search. We want another route. The score depends only on whether each pair of courses has the same sign or different signs, so we will record all of those pairwise relationships in a matrix. This will let us keep the same scoring rule while later allowing a broader set of relationship tables than exact timetables can produce. Start with the cut formula we already have: $$ \operatorname{cut}(s) =\frac12\sum_{i<j}W_{ij}(1-s_i s_j). $$ So far, $s_i$ has meant the sign assigned to course $i$. Write all ten signs as one column vector: $$ s= \begin{bmatrix} s_1\\ \vdots\\ s_{10} \end{bmatrix}, \qquad s_i\in\{-1,1\}. $$ Now define $d_i$ as the total conflict weight touching course $i$: $$ d_i=\sum_j W_{ij}. $$ The symbol $d$ means the column vector containing those ten totals, and $D$ means the diagonal matrix made from that vector: $$ d= \begin{bmatrix} d_1\\ \vdots\\ d_{10} \end{bmatrix}, \qquad D=\operatorname{Diag}(d_1,\ldots,d_{10}). $$ Finally, define $$ L=D-W. $$ Why does this matrix reproduce the cut score? Expand the matrix products one step at a time: $$ \begin{aligned} s^T Ls &=s^T(D-W)s \\ &=s^TDs-s^TWs \\ &=\sum_i d_i s_i^2-\sum_{i,j}W_{ij}s_i s_j. \end{aligned} $$ Every $s_i$ is either $-1$ or $1$, so $s_i^2=1$. Also, $d_i=\sum_jW_{ij}$. Therefore, $$ \begin{aligned} s^T Ls &=\sum_{i,j}W_{ij}-\sum_{i,j}W_{ij}s_i s_j \\ &=\sum_{i,j}W_{ij}(1-s_i s_j) \\ &=2\sum_{i<j}W_{ij}(1-s_i s_j) \\ &=4\operatorname{cut}(s). \end{aligned} $$ The factor $2$ in the third line appears because the sum over all $(i,j)$ counts each undirected conflict edge once as $(i,j)$ and again as $(j,i)$. We have now derived $$ \operatorname{cut}(s)=\frac14s^TLs. $$ The matrix $L=D-W$ is called the **weighted graph Laplacian**. Here, its name matters less than the calculation: the displayed expansion shows exactly how it gives the score we started with. We still have products such as $s_i s_j$. Give the complete table of those products a name: $$ X=ss^T= \begin{bmatrix} s_1s_1 & \cdots & s_1s_{10}\\ \vdots & \ddots & \vdots\\ s_{10}s_1 & \cdots & s_{10}s_{10} \end{bmatrix}. $$ Uppercase $X$ denotes a matrix, and its entry in row $i$, column $j$ is $$ X_{ij}=s_i s_j. $$ Thus $X_{ij}=1$ when courses $i$ and $j$ use the same slot, and $X_{ij}=-1$ when they use different slots. Every diagonal entry is $X_{ii}=s_i^2=1$. The matrix $X$ is simply a table of the pairwise slot relationships that the score uses. Expand the quadratic form once more: $$ s^TLs =\sum_{i,j}L_{ij}s_i s_j =\sum_{i,j}L_{ij}X_{ij}. $$ The last sum is abbreviated by $\langle L,X\rangle$: multiply corresponding entries of $L$ and $X$, then add the results. Hence $$ \operatorname{cut}(s)=\frac14\langle L,X\rangle. $$ Nothing in this identity has shortened the exact search. To find the best timetable with it, we could still take each of the 1,024 sign vectors, build its matrix $X$, and evaluate the score. We would have changed the calculation, but not the amount of searching. The matrix does reveal a new question: which pairwise-relationship tables can actually come from a two-slot timetable? For example, the three-course timetable $$ s= \begin{bmatrix} 1\\ 1\\ -1 \end{bmatrix} $$ produces $$ X=ss^T= \begin{bmatrix} 1 & 1 & -1\\ 1 & 1 & -1\\ -1 & -1 & 1 \end{bmatrix}. $$ Courses 1 and 2 share a slot, and course 3 occupies the other slot. Now consider a different table: $$ Y= \begin{bmatrix} 1 & -1 & -1\\ -1 & 1 & -1\\ -1 & -1 & 1 \end{bmatrix}. $$ It claims that every pair of courses occupies different slots. No two-slot timetable can do that for three courses. So a symmetric table with $1$ on its diagonal and $\pm1$ elsewhere is not automatically a valid timetable table. The pairwise claims must agree with one another. A matrix made as $X=ss^T$ is guaranteed to be consistent. For any three courses, $$ X_{ij}X_{jk} =(s_i s_j)(s_j s_k) =s_i s_k =X_{ik}, $$ because $s_j^2=1$. The impossible table $Y$ fails this check: it says courses 1 and 2 differ and courses 2 and 3 differ, which should force courses 1 and 3 to match, yet it says they differ too. ```{julia} #| label: laplacian-identity using LinearAlgebra signs = exact.best_signs incident_weights = W * ones(size(W, 1)) degree_matrix = Diagonal(incident_weights) laplacian = degree_matrix - W pairwise_products = signs * signs' direct = cut_weight(W, signs) quadratic = dot(signs, laplacian * signs) / 4 matrix_form = sum(laplacian .* pairwise_products) / 4 @assert direct ≈ quadratic ≈ matrix_form (direct, quadratic, matrix_form, diagonal = diag(pairwise_products), entries = sort(unique(pairwise_products))) ``` Why keep the matrix form if it does not yet reduce the search? The signs describe one timetable; $X$ exposes all of its pairwise relationships at once. Those products can also be read as inner products, which gives them a geometric meaning. Chapter 02 develops that geometry and asks how a matrix can store relationships among vectors. Only after that foundation will we change which matrices are allowed. ## Try it yourself 1. Complete `learner/01_searching_for_a_cut.jl` without calling `exact_maxcut`. 2. Verify the quadratic identity for five randomly generated sign vectors. 3. Add an eleventh course with one conflict edge. Predict how many distinct schedules enumeration will inspect. 4. Explain the difference between “the best schedule found” and “the best schedule,” and why enumeration closes that gap here.