{'fraction_non_alphanumeric': 0.04866887629637549, 'fraction_numerical': 0.019672832246338073, 'mean_word_length': 4.316130499033761, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semidefinite Programming in Timetabling and Mutual-Exclusion Scheduling

In scheduling and timetabling applications, the mutual-exclusion constraint stipulates that certain pairs of tasks that cannot be executed at the same time. This corresponds to the vertex colouring problem in graph theory, for which there are well-known semidefinite programming (SDP) relaxations. In practice, however, the mutual-exclusion constraint is typically combined with many other constraints, whose SDP representability has not been studied. We present SDP relaxations for a variety of mutual-exclusion scheduling and timetabling problems, starting from a bound on the number of tasks executed within each period, which corresponds to graph colouring bounded in the number of uses of each colour. In theory, this provides the strongest known bounds for these problems that are computable to any precision in time polynomial in the dimensions. In practice, we report encouraging computational results on random graphs, Knesser graphs, ``forbidden intersection'' graphs, the Toronto benchmark, and the International Timetabling Competition.

In scheduling and timetabling problems, one encounters extensions of the mutualexclusion constraint, which stipulates that certain pairs of tasks or events cannot be executed at the same time. This corresponds to the graph colouring problem in graph theory, for which there are well-known semidefinite programming (SDP) relaxations.
The SDP representability of combinations of the mutual-exclusion constraint with other constraints has been an open problem.
Clearly, the work on graph colouring provides a test of infeasibility for timetabling and scheduling problems incorporating the mutual exclusion problem. Such an infeasibility test compares a lower bound on the optimum of bounded vertex colouring of the conflict graph against the number of periods available. Lower bounds obtained in ignorance of the extensions, especially the bound on the number of uses of each colour, are still perfectly valid, but generally weak.
In this paper, we set out to explore applicability of semidefinite programming in scheduling and timetabling problems, which extend graph colouring. In educational timetabling, this corresponds to considering room sizes, room features, room stability, and pre-allocated assignments. In transportation timetabling, these correspond to considering vehicle capacity, line-vehicle compatibility, etc. We show that semidefinite programming relaxations of a variety of such problems can be formulated, starting with bounded vertex colouring of the conflict graph.
Our paper is organised as follows: Following some preliminaries, we present our relaxations in Section 3. In Section 4 we specialise a well-known first-order method to solving the relaxations and showcase two algorithms for rounding in the relaxations. In Section 5, we analyse some properties of the relaxations and the performance of algorithms applied to them. In Section 6, we present results of extensive computational tests. On conflict graphs from the International Timetabling Competition 2007, the Toronto benchmark, as well as on random graphs, we show the relaxations often provide the best possible lower bound and make it possible to obtain very good solutions by randomised rounding. On "forbidden intersections" graphs, we show the strength and weakness of the bound. Further avenues for research are suggested in Section 7.

Semidefinite Programming
Firstly, let us revisit the definition of semidefinite programming, which is a popular extension of linear programming. In linear programming (LP), the task is to optimise a linear combination c T x subject to m linear constraints Ax = b subject to the elementwise restriction of variable x to non-negative real numbers. Notice c is an n-vector, x is a compatible vector variable, b is an m-vector, and A is m × n matrix. One can state the problem also as: where linear operator A A (x) (parametrised by matrix A) maps vector x to a vector Ax, and x ≥ 0 denotes the element-wise non-negativity of x, x ∈ (R + ) n . The element-wise non-negativity of x should be seen as a restriction of vector x to the positive orthant, which is a convex cone, as all linear combinations with non-negative coefficients of element-wise non-negative vectors are element-wise non-negative vectors. Using a variety of methods, linear programming can be solved to any fixed precision in polynomial time. These methods work for other symmetric convex cones as well. Semidefinite programming (SDP, Bellman & Fan, 1963;Alizadeh, 1995;Wolkowicz et al., 2000Wolkowicz et al., , 2000Anjos & Lasserre, 2011) is a convex optimisation problem, which generalises linear programming. It replaces the vector variable with a square symmetric matrix variable and the polyhedral symmetric convex cone of the positive orthant with the non-polyhedral symmetric convex cone of positive semidefinite matrices. The primal-dual pair in the standard form is: where X is a primal variable in the set of n × n symmetric matrices S n , y and S are the corresponding dual variables, b is an m-vector, C, A i are compatible matrices, and linear operator A A (X) (parametrised by a symmetric matrix A) maps a symmetric matrix X to vectors in R m , wherein the ith element A A (X) i = A i , X . A * A (y) is again the adjoint operator. M N or M − N 0 denotes M − N is positive semidefinite. Note that an n × n matrix, M, is positive semidefinite if and only if y T My ≥ 0 for all y ∈ R n . One can also treat inequalities explicitly in the primal-dual pair: where d is a q-vector and linear operator A B (X) maps n × n matrices to q-vectors similarly to A A above. As all linear combinations with non-negative coefficients of positive semidefinite matrices are positive semidefinite, X 0 should again be seen as a restriction to a convex cone.

Semidefinite Programming Relaxations of Graph Colouring
Graph colouring, also known as vertex colouring, or partition into independent sets, is the problem of:

GRAPH COLOURING
Given an undirected graph G = (V, E) with vertices V = 1, 2, . . . , n and edges E ⊂ {(u, v) s. t. 1 ≤ u < v ≤ n}, return a partition P = (P i ) of V of the smallest possible cardinality |P| so that for each partition P i , for no edge (u, v) ∈ E, there are both u and v in P i . As in any partition, ∪ i P i = V and for all 1 ≤ i < j ≤ |P|, we have P i ∩ P j = / 0.
The partitions are known as "colour classes" or "independent sets" in graph colouring, or (assignment to) "time periods" in timetabling and scheduling. The optimum, i.e., the smallest possible number |P| of colour classes, is denoted the "chromatic number" in graph colouring or minimum number of required time periods in timetabling, or "makespan" in connection with certain mutual-exclusion problems (cf. Section 3.1) in the scheduling literature.
The decision version of graph colouring appears on Karp's original list (Karp, 1972) of NP-Complete problems. In polynomial time, one can obtain lower bounds on the chromatic number, for instance using linear or semidefinite programming. Just as there are a number of ways of formulating a lower bound on the chromatic number in linear programming, there are a number of ways of formulating a lower bound on the chromatic number using SDP. All are, in some sense, related to the inequality of Wilf (Wilf, 1967), wherein the largest eigenvalue of an adjacency matrix of a graph incremented by one bounds the chromatic number of a graph from the above. By considering the semi-definite programming lower bound on the largest-eigenvalue upperbound, one obtains a parameter of a graph, sometimes known as 'theta', θ , (Lovász, 1979), which is at least as large as the clique number and no more than the chromatic number, yet is computable in polynomial time using SDP. The known bounds for colouring form a hierarchy (Szegedy, 1994): where α is the size of the largest independent set, ω is the size of the largest clique, χ is the chromatic number, X (G) = θ (Ḡ) is the vector chromatic number (Lovász, 1979;Karger, Motwani, & Sudan, 1998), X (G) = θ 1/2 (Ḡ) is the strict vector chromatic number (Kleinberg & Goemans, 1998), X + (G) = θ 2 (Ḡ) is the strong vector chromatic number (Szegedy, 1994), and bar indicates complementation of a graph. In Figure 1, we summarise all three formulations for all three lower bounds in the vector programming notation. None of the formulatons has, however, been extended to bounded colouring, up to the best of our knowledge.
Lovász's Bound as VP Kleinberg's Bound as VP Szegedy's Bound as VP Dual SDP of Szegedy's Bound There are a number of ways of deriving and thinking about the SDP relaxations. In any case, the primal n × n matrix variable can be seen as Notice matrix M has the "hidden block diagonal"property: Proposition 1 For any value of M, there exists a permutation matrix P, such that where J c is the c × c matrix of all ones and ∑ s i=1 c i = n. Such P T MP is denoted a direct sum of J c .
One can hence derive the semidefinite programming relaxation from: Proposition 2 ( Dukanovic and Rendl (2004)) For any symmetric 0-1 matrix M there exists a permutation matrix P such that P T MP is the direct sum of s all-ones matrices if and only if there is a vector of all-ones on the diagonal and the rank of M is s and M is positive semidefinite.
by relaxing the rank constraint, as usual (Fazel, Hindi, & Boyd, 2004). Alternatively, one can see theta as an eigenvalue bound, where the largest eigenvalue λ max (A) = min{t s. t. tI − A 0} for an identity matrix I. Perhaps most "fundamentally", one could see theta as a relaxation of the co-positive programming formulation of graph colouring, recently proposed by Bomze, Frommlet, and Locatelli (2010). A number of other derivations have been surveyed by Knuth (1994).

Related Applications
Within the job-shop scheduling, SDP relaxations of the maximum cut problem (MAX-CUT, Goemans & Williamson, 1995) have been adapted to scheduling workload on two machines (Skutella, 2001;H. Yang, Ye, & Zhang, 2003) and home-away patterns in sports scheduling (Suzuka, Miyashiro, Yoshise, & Matsui, 2007). (Bansal, Srinivasan, & Svensson, 2016) extended this to scheduling with weighted completion time objectives on any number of unrelated machines, using a clever rounding technique in a lift-and-project relaxations. They have also shown that the relaxation of (Skutella, 2001) is in some sense weak (has 3/2 integrality gap). We are not aware of any applications of semidefinite programming to mutual-exclusion scheduling or timetabling, excepting two abstracts of the present authors (Burke, Marecek, & Parkes, 2010;Marecek & Parkes, 2012), which we build upon in this paper.

Mutual-Exclusion Scheduling
In one of the prototypical problems in timetabling, scheduling, and staff rostering (Welsh & Powell, 1967;Burke, de Werra, & Kingston, 2004;Baker & Coffman, 1996), one needs to assign n unit-time events, classes, tasks, or jobs ("vertices"), some of which must not be run, executed, or taught at the same time ("the mutual-exclusion constraint"), perhaps due to the use to some shared, renewable resource, to m rooms, processors, machines, or employees ("uses of a colour"), so that the number of units of time required ("makespan", "number of colours") is as small as possible. It is natural to represent the elements being assigned by the elements of set V = 1, 2, . . . , n, and to represent the mutual-exclusion constraint by a set of pairs of elements of V , which are not to be assigned to disjoint time-units ("conflict graph").
Let us now consider:

m-BOUNDED COLOURING
Given an undirected graph G = (V, E) with vertices V = 1, 2, . . . , n and edges and an integer m ≤ |V |, return a partition P = (P i ) of V of the smallest possible cardinality |P| so that for each partition P i , |P i | ≤ m and for no edge (u, v) ∈ E there are both u and v in P i .
From the block-diagonal property of the matrix variable (12), it seems clear that we expect row-sums and column-sums in the binary-valued variable to be bounded from above by m: where X is an n × n matrix variable and t is a scalar variable. By dropping the element-wise integrality, relaxing a non-convex bound on rank(X) to a convex bound on the trace(X), and algebraic manipulations, we obtain the relaxation: where Y is an n × n matrix variable and t is a scalar variable. This can be seen as a spectahedron (E1-PSD) being intersected by a polyhedron given by the linear inequalities (IN). Notice that additional inequalities ∑ v∈V Y uv ≤ tm ∀u ∈ V are not required due to symmetry. Notice also that the usual theta-like relaxations (X (G), X (G), X + (G)) cannot be used easily, as one cannot easily work with a graph's complement, both due to its density and due to the constraints on the representability of our extensions.
The complication is the relaxation above is not a semidefinite program in the standard form (P STD, D STD). Notice scalar variable t has been introduced only for clarity. As long as the entries on the diagonal of the matrix variable are constrained to be equal, any one of them can be used instead. One can either introduce new scalar slack variables and convert inequalities to equalities, or one can design solvers treating inequalities explicitly.
There remains the constraint Y − J 0 to deal with, as the standard form only allows to require a matrix, rather than expression, to be psd. The mechanistic approach, employed by automated model transformation tools (Löfberg, 2004), for instance, is to double the dimension by introducing new variable X, set Y − J = Z, Z 0. For an arbitrary vertex w ∈ V , one obtains: An alternative approach is to optimise: Any formulation involving Y − J in this paper can be easily transformed in this fashion.

Initial Assignment
In many applications, one has to deal with complicating constraints. In graph-theoretic terms, the most common complicating constraints are pre-existing assignments. Preexisting assignments can be represented as subsets of V , which need to be assigned to the same unit of time. This corresponds to: m-BOUNDED COLOURING WITH PRE-COLOURING Given an undirected graph G = (V, E) with vertices V = 1, 2, . . . , n and edges the smallest possible cardinality |P| so that for each partition P i , |P i | ≤ m and for no edge (u, v) ∈ E there are both u and v in P i and for each set C i ∈ C, there is a partition in C i ⊆ P j ∈ P. The graph G is called "conflict graph" and family C is called "pre-colouring". The partition P corresponds to the "same-colour equivalence" and P i are called "colour classes" or "independent sets".
In terms of complexity theory, m-Bounded Colouring with Pre-Colouring is NP-Hard even on trees (Bodlaender & Fomin, 2005). Even in the case of trees, however, there are fixed parameter tractable algorithms (Bodlaender & Jansen, 1993;Bodlaender & Fomin, 2005).
In terms of SDP representability, given a pre-colouring C = (C i ),C i ⊆ V , it suffices to set the corresponding elements of matrix variable Y to t:

A Reformulation
As an aside, notice that m-BOUNDED COLOURING WITH PRE-COLOURING can be easily transformed into a problem without pre-colouring, but with certain weights on vertices: c-WEIGHTED m-BOUNDED COLOURING Given an undirected graph G = (V, E) with vertices V = 1, 2, . . . , n and edges E ⊂ {(u, v) s. t. 1 ≤ u < v ≤ n}, a vector of positive integers c of dimension |V |, and an integer m ≤ |V |, return a partition P = (P i ) of V of the smallest possible cardinality |P| so that for each partition P i , cp i ≤ m, where p i is the 0 − 1 index vector corresponding to P i , and for no edge (u, v) ∈ E there are both u and v in P i .
For any non-empty C, this leads to a reduction in the dimension of the matrix variable, compared to the simple relaxation (17): While the reduction improves computational performance, when used with off-theshelf solvers, it may render both the design of custom solvers and their analysis (cf. Section 5) more challenging.

Simple Laminar Timetabling
In timetabling applications, it is often necessary to consider assignment of events to both periods and rooms. In the relaxations above, vertices within a single colour class correspond to events taking place at the same time, but rooms are represented only by the m-bound, which corresponds to the number of room available. This may be insufficient: Consider, for example, a situation with two large lecture rooms, twenty periods per week, and forty large lectures. One could formulate this problem as a binary linear program with a variable with three indices (events, rooms, and periods) and apply the operators of Lovász and Schrijver (1991) or Lasserre (2001) to obtain semidefinite programming relaxations. We present a number of alternatives, where the matrix variable has a considerably lower dimension.
In particular, one can extend m-BOUNDED COLOURING WITH PRE-COLOURING to consider not only the number m of available rooms (processors, machines, employees, or similar), but also their capacities and features. This corresponds to:

SIMPLE TIMETABLING
Given an undirected conflict graph G = (V, E) where vertices V are also denoted events, a vector of capacity-requirements p ∈ R |V | , an integer m ≤ |V |, a vector of capacities r ∈ R m , a number of features f ∈ N, set F ⊆ V × F detailing feature-requirements of events, set G ⊆ {1, 2, . . . , m} × F detailing feature availability, and a family C = (C i ) of disjoint subsets of V with |C i | ≤ m, return a partition P = (P i ) of V of the smallest possible cardinality |P| so that • for each partition P i , |P i | ≤ m • for each partition P i and for no edge (u, v) ∈ E there are both u and v in P i • for each partition P i and for each distinct capacity c in r, the subset of P i with capacity greater or equal than c, according to p, is less than the number of elements in r greater or equal to c • for each partition P i and for each feature 1, 2, . . . , f , the subset of P i requiring the feature, according to F, is less than the number of rooms where it is available, according to G • for each set C i ∈ C, there is a partition in C i ⊆ P j ∈ P.
In an important special case, which we denote SIMPLE LAMINAR TIMETABLING, sets of events and rooms with certain feature-requirements and feature-availability 0. The subsets of rooms requiring capacities larger than a certain value are naturally laminar, but naturally occurring features need not be. As m-Bounded Colouring with Pre-Colouring is a special case of Simple Laminar Timetabling, hardness results cited above apply also to Simple (Laminar) Timetabling. Such laminar timetabling and associated bounds can be of interest, for example, in planning the capacities of rooms cf. (Beyrouthy, Burke, McCollum, McMullan, & Parkes, 2010).
Initially, we restrict ourselves to the Simple Laminar Timetabling and extend the c-weighted relaxation above (18). Let us suppose n vertices V of the conflict graph correspond to n events attended by p 1 , p 2 , . . . , p n persons each, whereas the m-bound corresponds to rooms of capacities r 1 , r 2 , . . . , r m . Let us denote distinct distinct numbers of persons attending an event P, L(p) the events of size s > p and R(p) the rooms of capacity r > p. Clearly, one can add two constraints (PR1, PR2) for each element of P: Notice the newly added constraints (PR1, PR2) subsume the linear inequalities (L1, L2) of the relaxations above. There is always a feasible solution, and as will be shown in Section 5.3, one can efficiently produce feasible timetables satisfying those constraints from the value of the matrix variable.
Considering there is always a permutation matrix such that the matrix variable is block-diagonal (12), one can also add bounds obtained by counting arguments. The simple counting bound is ∑ u,v∈V Y uv ≤ m|V |. Indeed, there are at most |V |/m blocks of m 2 non-zeros each. One can generalise the bound to subsets P of events: In SIMPLE LAMINAR TIMETABLING, one can include feature considerations similarly to capacity considerations. In a slight abuse of notation, we use F( f ) to denote the set of events requiring feature f and G( f ) the set of rooms with feature f .
Notice, however, the limitation to the laminar special case.

Simple Timetabling
A natural approach to formulating the Simple Timetabling Problem without laminarity requirements uses the additional variables: Z u,v,r = 1 if vertex u is in the same colour class as v and v is assigned (room) r 0 otherwise.
The additional constraints follow. In timetabling language: an event v is assigned a room in Z u,v,r for some r if and only if it is assigned time in Y u,v (23), no event is assigned to two rooms (24), no two events share a room (25) and Z u,v,r = 0 if the eventroom combination does not match the event's room-feature or capacity requirements (26,27).
This results, however, in relaxations too large to be handled by solvers currently available. An alternative approach uses fewer additional variables: The additional constraints follow. In timetabling language: each event is in exactly one room (30, 31), events in the same timeslot do not share rooms (32), and R v,r = 0 if the event-room combination does not match the event's room-feature or capacity requirements (33,34).
Notice that the encoding makes it possible to formulate room stability constraints and penalties, as it is invariant to "timeslot permutations". For example, the hard constraint reads R v,r + R v ,r ≤ t for all suitable v = v and all r = r .

Algorithms
While our key contribution are the actual relaxations, we showcase how these can be used in state-of-the-art algorithms. Such algorithmic applications of the relaxations underlie not only our computational results, but also our analytical results in Section 5.

Solving the Relaxations
First, let us consider a first-order method based on the alternating-direction method of multipliers (ADMM) on an augmented Lagrangian, following the extensive literature (Malick, Povh, Rendl, & Wiegele, 2009;Burer & Vandenbussche, 2006;Zhao, Sun, & Toh, 2010;Povh, Rendl, & Wiegele, 2006;Wen, Goldfarb, & Yin, 2010;Goldfarb & Ma, 2010;L. Yang, Sun, & Toh, 2015). In order to distinguish between equality constraints reflecting the structure of the conflict graph (A 1 ) and the remainder of the equality constraints (A 2 ), let us consider the primal-dual pair: with the linear operator A A (X) mapping matrix X and matrix A to vector as in the definition of SDPs in Section 2.1. The augmented Lagrangian of the dual (36) is then: In an alternating direction method of multipliers, one minimises the augmented Lagrangian in v, S, and (y 1 , y 2 ), in turns, as suggested in Algorithm Schema 1. In general, Algorithm Schema 1 reduces the minimisation of one moderately complicated convex optimisation problem to solving three simpler convex optimisation subproblems. In Line 8, one can solve the linear system given by first-order Karush-Kuhn-Tucker optimality conditions of arg min v∈R q ,v≥0 In Line 9, it is important to realise that arg min Algorithm Schema 1 AugmentedLagrangianMethod(A 1 , A 2 , B,C, b 1 , b 2 , d) 1: Input: Instance I = (A 1 , A 2 , B,C, b 1 , b 2 , d) of SDP, precision ε(36) 2: Output: Primal solution Y , computed up to ε-precision 3: Set iteration counter k = 0 4: Initialise X k 0 with a heuristically obtained colouring 5: Compute matching values of dual variables y k 1 , y k 2 , v k ≥ 0, and S k 0 6: while the precision is insufficient do 7: Increase iteration counter k 8: Update v k+1 = arg min v∈R q ,v≥0 L µ (X k , y k+1 1 , y k+1 2 , v, S k ) 9: Update S k+1 = arg min S 0 L µ (X k , y k+1 1 , y k+1 2 , v k+1 , S) 10: (y k+1 1 , y k+1 2 ) = arg min y 1 ∈R m ,y 2 ∈R m L µ (X k , y 1 , y k 2 , v k , S k )

11:
Choose any step-length µ ≥ 0 12: 13: end while 14: Return X can be solved by spectral decomposition of the term subtracted from S (Stewart, 1993). Finally, in Line 10, one can initialise the computation with: We refer to (L. Yang et al., 2015) for a some excellent suggestions as to the implementation of the linear solver and spectral decomposition, as well as convergence properties of such as method.

Recovering an Assignment
Let us comment on the recovery of an upper bound from the lower bound provided by SDP. Since the seminal paper of Karger, Motwani, and Sudan (Karger et al., 1998), there has been a continuing interest in algorithms recovering a colouring from semidefinite relaxations. Typically, such algorithms are based on simple randomised iterative rounding of the semidefinite programming relaxation. One such algorithm, specialised to simple timetabling is displayed in Algorithm Schema 2. Alternatively, one can consider methods solving a sequence of smaller semidefinite programming relaxations, inspired by the so-called iterated rounding in linear programming (Lau et al., 2011). When applied to linear programming, the method fixes variables, whose values in the relaxation are close to 0 or 1, to 0 or 1, respectively, and resolves the smaller residual linear program. When applied to semidefinite programming, the method fixes eigenvectors whose corresponding eigenvalues are close to zero or one. Let us consider the example of (Morgenstern, Samadi, Singh, Tantipongpipat, Algorithm Schema 2 Rounding(X) based on Karger, Motwani, and Sudan 1: Input: Matrix variable X of the solution to the SDP (17) of dimensions n × n, bound m, number a max of randomisations to test, plus the input to Simple Timetabling, if required 2: Output: Partition P of the set V = 1, 2, . . . , n 3: Compute vector v, X = v T v using Cholesky decomposition 4: for Each attempted randomisation a = 1, . . . , a max do 5: while There are uncoloured vertices in X do 7: Pick a suitable c = 2(k−2) k log e ∆ for ∆ being the maximum degree of the vertices in X which can accommodate many of the SDP relaxations we have seen so far. There, (Morgenstern et al., 2019) initialise F 0 = F 1 = / 0 and F = I n . In each iteration, subspaces spanned by eigenvectors corresponding to eigenvalues 0 or 1 are fixed and the corresponding standard basis vectors are moved from F to F 0 and F 1 , respectively. Thus, one increases the subspaces spanned by columns of F 0 and F 1 , while maintaining pairwise orthogonality. To obtain new F, one solves a smaller semidefinite program in r × r symmetric matrix X(r): which assures that, eventually, we can recover X that is orthogonal to all vectors in subspace spanned by vectors in F 0 , and whose eigenvectors corresponding to eigenvalue 1 For any eigenvector v of X * (r) with eigenvalue less than δ , let F 0 ← F 0 ∪ {Fv}.

10:
Update F by taking every eigenvector v of X * (r) with eigenvalue within [δ , 1 − δ ], and taking Fv to be the columns of F. 11: end while 12: From rank-t matrix F 1 F T 1 reconstruct partition P by Cholesky decomposition will be the columns of F 1 . This is summarised in Algorithm Schema 3. As we will see in Section 5.3, this allows for non-trivial performance guarantees. As a remark, we note that there are many other alternative rounding approaches within the Theoretical Computer Science literature. We refer to (Barak, Raghavendra, & Steurer, 2011;Raghavendra & Tan, 2012;Bansal et al., 2016;Abbasi-Zadeh et al., 2018) for notable examples. While they may not be directly applicable, they are based on important insights that would be applicable.

An Analysis
Next, let us analyse the strength of the bound and the complexity of computing it, both of which affect its practicality.

The Strength of the Bound
In terms of strength of the bound, one can extend a number of properties of relaxations of graph colouring to bounded colouring. For the sake of completeness, we reiterate some of them. For instance, one can show the sandwich-like: Proposition 3 For every graph G, there is an m ≥ 0, such that where ω is the size of the largest clique, χ is the chromatic number, C is a bound obtained by counting, χ m is the m-bounded chromatic number, the values of SDP relaxations follow the notation of Figure 1 and Y + is the strengthening of Y + (G, m) with triangle inequalities.
Proof (sketch) The relationship between the values of the successive relaxations of bounded colouring is clear. To show there is m, such that χ(G) ≤ C (G, m), let us study two cases: If there is r ≥ 1 such that r-bounded graph colouring of G requires a strictly larger number of colour classes than the chromatic number, take m = r. Otherwise, the graph cannot have independent sets larger than one, hence is a clique, and ω(G) = χ(G) = χ(G, m) for any m.
To see that (non-bounded) graph colouring relaxations (X (G), X (G), X + (G)) provide only very weak bounded graph colouring relaxations, consider empty graphs on n vertices and the constant function f (n) = 1: Proposition 4 There is an infinite family of graphs and f (n), where the chromatic number is O(1), the f (n)-bounded chromatic number is O(n).
In contrast, the value of the semidefinite programming relaxation of bounded colouring may match the bounded chromatic number on such graphs.
On random graphs where an edge between each pair of distinct vertices appears with probability p, independent of any other edge, which are known as Erdős-Rényi G(n, p): Proposition 5 With probability 1 − o(n), graph G drawn randomly from G n,p has where the big-O notation hides lower-order terms.
Proof (sketch) The proof combines the sandwich-like Property 3 and the impressive result of Juhász (1982).
Computationally, this bound seems to be rather tight, as we show in Section 6.

The Structure of the Relaxations
For example, let us consider the formulation of bounded graph colouring (15) for a graph on n vertices and m edges. There equality constraints reflecting the structure of the conflict graph (A 1 ) have the cardinality of their support (number of non-zero elements) equal to the number of edges in the conflict graph and the remainder of the equality constraints (A 2 ) also have a very simple structure: Proposition 6 First m equalities (A1) correspond to m × n 2 matrix A 1 . A 1 A T 1 = I m , where I m is the m × m identity matrix.
Proposition 8 Inequalities (B) correspond to n × n 2 matrix B = I ⊗ j, where j is the row-vector of n ones. Hence, BB T = nI n , where I n is the n × n identity matrix. For an n-element column-vector v, B T v = (v ⊗ j) T = [v 1 j v 2 j · · · v n j] T , where j is the rowvector of n ones.
Proposition 9 The elements of the objective matrix C are zeros except for C 1,1 = 1. Hence A A 1 (C) = 0, where 0 is the m-vector of zeros. A A 2 (C) = j, where j is the (n − 1)-vector of ones.

Across both:
• custom solvers, such as Algorithm Schema 1 and the three sub-problems in Lines 8-10, in particular, and • general-purpose solvers allowing for the input of block-structured matrices with sparse and identity blocks, such as (Fujisawa, Fukuda, Kojima, & Nakata, 2000;Gondzio & Grothey, 2009), it is possible to exploit Properties 6-8 so as to: • evaluate the augmented Lagrangian and its gradient at a given v in time n 2 in relaxations of bounded graph colouring of a graph on n vertices, compared to O(n 6 ) run-time of methods not exploiting the structure.

The Recovery
Due to the hardness of approximation of colouring in a graph with large enough a chromatic number within the factor of n ε for some fixed ε (Zuckerman, 2007), one cannot hope to guarantee reconstruction of a solution close to optimality in the worst case. Having said that, as we will illustrate in the next section, however, Algorithm Schema 2 performs rather well in practice.
One can also provide weaker guarantees. In particular, one could consider the socalled ε-solution, which satisfies linear constraints within an additive error of ε, while being at most ε from the optimal objective. Notice that the fact that an ε-solution is obtainable in time polynomial in n and log 1 ε does not contradict the hardness of approximation results (Zuckerman, 2007), which consider the objective of solutions satisfying the constraints exactly.
Proposition 10 There exists an ε > 0 and an algorithm implementing Algorithm Schema 3 that, given any feasible solution to the SDP relaxation (21) of SIMPLE LAMINAR TIMETABLING, runs in time polynomial in n and log 1 ε and returns an ε-feasible and ε-optimal solution to the SDP relaxation (21) of SIMPLE LAMINAR TIMETABLING.
Proof (sketch) The proof extends the work of (Morgenstern et al., 2019) on the number of fractional eigenvalues in any extreme point X of a suitable form of a semidefinite program with m linear inequalities and trace bounded by t, which is Based on this bound, one can formulate a generic result on iterative rounding of SDPs, which we present in Proposition 11 below. The result applies to the SDP relaxation (21) of SIMPLE LAMINAR TIMETABLING, because it can be cast into the suitable form (42). The bound on the run-time follows from the fact we solve at most n semidefinite programs in matrices at most n × n and standard results on interior-point methods (Alizadeh, 1995).
Proposition 11 (Theorem 7 of (Morgenstern et al., 2019)) Let C be a n × n matrix and {A 1 , . . . , A m } be a collection of n × n real matrices, d ≤ n, and b 1 , . . . , b m ∈ R.
Suppose the semi-definite program (42) with a trace bounded by d and m other constraints has a nonempty feasible set and let X * denote an optimal solution. There is an algorithm that given a matrix X 0 that is a strictly feasible solution, returns a matrixX such that 1. rank ofX is at most d, 2. C,X ≤ C, X * , and 3. for each index 1 ≤ i ≤ m of a constraint we have where σ i (S) is the i th largest singular of the average of matrices 1 |S| ∑ i∈S A i for any subset of matrices defining the constraints, S ⊆ {1, . . . , m}.
In the violation bound (48), the quantity σ i (S) is non-trivial to reason about, but it is clear that it is rather modest, because the singular values are at most 1 and the summation goes over at most √ 2m + 1 values.

Computational Experience
To corroborate our analytical results in Section 5, we have conducted a variety of computational tests. Most of these have been driven by YALMIP (Löfberg, 2004) scripts running within MathWorks Matlab R2017b on a laptop with Intel Core Duo i5 at 2.7 GHz with 8 GB of RAM, which also had IBM ILOG CPLEX 12.8 and SeDuMi 1.3 (Sturm, 1999) installed. Let us refer to it as a laptop. When explicitly mentioned, we also present results obtained on a machine equipped with 80 cores of Intel Xeon E7-8850 at 2.00 GHz and 700 GB of RAM, which had MathWorks Matlab R2016b, IBM ILOG CPLEX 12.6.1, and SeDuMi 1.3 (Sturm, 1999) installed. Let us refer to it as a large-memory machine.

A Motivating Example
As a first concrete computational example, we consider a small conflict graph from a standard collection of benchmark problems in timetabling. Specifically, we take the instance sta-f-83 from the Toronto examination timetabling benchmarks 1 . There are 139 events, but the conflict graph has three connected components of 30, 47 and 62 vertices. Here, we use the 47-vertex component. The results are given in Table 1, with bounded chromatic numbers obtained using the most straightforward integer linear programming formulation solved using the default settings of IBM ILOG CPLEX on a laptop. Firstly, note that m = 1 gives precisely the number of nodes, as would be expected. Secondly, note that Y m is generally much tighter than the lower bound |V |/m obtained by simple counting arguments. Accidentally, Y m lower bounds actually happen to match the optima in this particular instance. For example, at m = 5, counting cannot rule out a 10-colouring, but the SDP bound shows that at least 14 colours are required. As far as we know, SDP relaxations are the only way to get such information in polynomial time, considering that the 14-colouring together with a certificate of its optimality can be obtained using CPLEX, but not in polynomial time.

Random Graphs
Next, we show that the same behaviour can be observed on a large sample of random graphs.
First, we demonstrate the improved strength of the lower bound obtained from semidefinite programming as the restriction on the number of uses of a colour is tightened (i.e., cardinality of a colour class is bounded from above by progressively smaller numbers). In general, we compute the best possible vertex colouring, without any bound on the number of uses of a colour, and take the size of the largest colour class to be C. Subsequently, we obtain lower bounds, upper bounds, and optima for (C − 1)bounded colouring, (C − 2)-bounded colouring, etc., of the same graph. In particular, we use random graphs with constant probability 0.5 of an edge appearing between a pair of distinct vertices and varying numbers n of vertices, which are known as G(n, 1 2 ). For each number n of vertices, we have generated 100 random graphs, computed the true chromatic numbers and the size of the largest colour class C using CPLEX, lower bounds on the bounded colouring using SeDuMi, and upper bounds by rounding the semidefinite programming relaxation, all running on a laptop. In Figure 2, the true value is plotted in a solid line, while a semi-transparent region spans the lower and upper bounds. Notice that: In Figure 2, the true value is plotted in a solid line, while a semi-transparent region spans the lower and upper bounds. Notice that: • the upper bounds obtained by rounding the semidefinite programming relaxation coincides with the true value obtained by ILOG • for unbounded and (C − 1)-bounded colouring, there is a considerable gap between the SDP-based lower bound and the true value • for (C − 3)-bounded colouring, the SDP-based lower bound and the true value coincide in the majority of cases. (That is: One can round the upper bound up, as it has to be integral. The average over 100 samples need not be integral, though.) • for (C − 3)-bounded colouring, the SDP-based lower bound is essentially tight.
Second, we illustrate the practicality of the approach by illustrating the dependence of the run-time on dimensions of the graph. Figure 3 presents the results on instances, which fit within the memory of a laptop. It suggests that run-time of commonly used first-order methods for solving semidefinite-programming relaxations increases linearly with the number of vertices of the graph, while the run-time of commonly used second-order methods for solving semidefinite-programming relaxations increases quadratically with the number of vertices of the graph. This is surprising. Consider the fact that the dimension of the matrix variable increases quadratically with the number of vertices and the number of elements in the Hessian matrix considered in second-order methods increases quadratically in the dimension. In both cases, the observed run-time is due to the ability of the respective methods to exploit the structure of Section 5.2. Figure 4 presents the corresponding results on instances, which no longer fit within the memory of a laptop, as run on a large-memory machine. We note that already on a random graph on 200 vertices, G(200, 0.5), SeDuMi regularly consumes over 24 GB physical memory, with further 13 GB in swap, in solving the SDP relaxation of bounded graph colouring. Although the run-times are longer, considering the sheer amounts of data processed, the evolution of run-time as a function of the number of vertices seems similar to Figure 3. Figure 5 illustrates that commonly used methods do not exhibit a major increase in run-time as the density of the graph increases, due to their ability to exploit the structure of Section 5.2. Again, this is surprising. Consider that the number of edges in the conflict graph asymptotically approaches the square of the number of vertices in a dense graph. If there were no structure, the cubic increase of run-time with each of the quadratic number of constraints may render the approach impractical. In particular, we use random graphs of varying densities, all on 100 vertices. The data are again available on-line. For each of the densities p = 0.1, 0.2,. . . , 0.9%, we have generated 100 graphs G(40, p). Subsequently, we have obtained SDP-based lower bounds using 4 different methods: IPM a standard implementation of a primal-dual interior point method (IPM) by (Sturm, 1999) DimRed a dimension-reduction procedure of (Löfberg, 2004) followed by the IPM of (Sturm, 1999) SparseCoLo a sparsity-exploiting procedure of (Kim, Kojima, Mevissen, & Yamashita, 2011) followed by the IPM of (Sturm, 1999) AugLag an implementation of a first-order method considering the augmented Lagrangian, based on (Zhao et al., 2010;L. Yang et al., 2015) For each of the methods, and each of the densities p, we report the average run-time over 100 graphs.

Conflict Graphs from Timetabling Benchmarks
As a further illustration of the strength of SDP lower bounds, we present lower bounds for conflict graphs from two timetabling benchmarks. From instances used in Track 3 of International Timetabling Competition 2007, we have extracted course-based conflict graphs, where there is edge between two vertices, if there is a curriculum prescribing the enrollment in both corresponding courses, or if a single teacher teaches both courses. For details, please see (Bonutti, De Cesco, Di Gaspero, & Schaerf, 2012) or (Burke, Mareček, Parkes, & Rudová, 2012). From Toronto Examination Timetabling Benchmark, we have extracted exam-based conflict graphs, where there is edge between two vertices, if there is a student who should sit both corresponding exams. For details, please see (Qu, Burke, McCollum, Merlot, & Lee, 2009). For each graph, we have computed the best possible vertex colouring, without any bound on the number of uses of a colour, and took the size of the largest colour class to be C. Subsequently, we have obtained lower bounds, upper bounds, and optima for (C − 1)-bounded colouring, (C − 2)-bounded colouring, etc.

Two Examples of Theoretical Interest
To illustrate the weakness of the bound on certain graphs, we present the results for Knesser graphs of Lovász (Lovász, 1978) and the "forbidden intersections" graphs of Frankl and Rödl (Frankl & Rödl, 1987). Knesser graph K(n, k), n > k > 1, has n k vertices, corresponding to subsets of {1, 2, . . . , n} of cardinality k. Two vertices are adjacent if the corresponding subsets are disjoint. Lovász has shown (Lovász, 1978) the chromatic number of K(n, k) is exactly n − 2k + 2, despite the fact K(n, k) has no triangle for n > 3k. Similarly, forbidden intersections graph F(m, γ), m ≥ 1, 0 < γ < 1, such that (1 − γ)m is an even integer, has 2 m vertices, corresponding to sequences of m bits (zeros and ones). Two vertices are adjacent, if the corresponding sequences differ in precisely (1 − γ)m bits. It is known the theta bound of Lovász and related semidefinite programming relaxations of graph colouring perform poorly on both "forbidden intersections" (Charikar, 2002) and Knesser graphs (Karger et al., 1998): the lower bound is O(1) as n grows, whereas the actual chromatic number grow O(n) with n. Table 3 shows the lower bound gets tighter as the bound on the number of uses of a colour gets tighter.
It should be noted that there is a large difference between clique and chromatic numbers in both Knesser and forbidden intersection graphs, which makes them quite unlike conflict graphs encountered in timetabling applications. Although semidefinite programming lower bounds for graph colouring are weak on these graphs, they do tighten, as the bound on the number of uses of colours tightens. Nevertheless, the proposed lower bound is far from tight, in the worst case.

Conclusions
This paper has explored the limits of representability of extensions of graph colouring in semidefinite programming (SDP). SDP clearly provides some of the strongest known relaxations in timetabling. In particular, relaxations of simple timetabling problems related to Lovász theta provide useful lower bounds on the number of periods required in the timetable, considering the conflict graph, the number of rooms, the capacities of rooms and special equipment available therein, and a pre-assignment of certain events to certain periods.
In such low-dimensional SDP relaxations, the colour assignment is not represented directly, but only in terms of the classes of equivalence of nodes assigned the same Table 3: For Knesser graphs K(n, 2) and forbidden intersection graphs F(n, γ), where the size of the largest colour class in an optimal colouring is C, lower bounds Y m and optima χ m for (C − m)-bounded colouring are shown. For m = 0, no bounds were applied.
Graph Y 0 χ 0 Y −1 χ −1 Y −2 χ −2 Y −3 χ −3 K(5, 2) 2.50 3 3.33 4 5.00 5 10.00 1 K(6, 2) 3.00 4 3.75 4 5.00 5 7.50 8 K(7, 2) 3.50 5 4.20 5 5.25 6 7.00 7 K(8, 2) 4.67 6 5.60 6 7.00 7 9.33 10 FI(6, 0.50) 2.00 2 2.03 3 2.06 3 2.13 3 FI(6, 0.67) 6.40 7 7.11 8 8.00 8 9.14 10 FI(6, 0.83) 2.00 2 2.03 3 2.06 3 2.13 3 FI(6, 1.00) 2.00 2 2.00 2 2.06 3 2.13 3 colour. This is sufficient for simple timetabling problems as described above, and makes the representation naturally invariant under the permutation of the colours. In contrast, many objectives in timetabling refer to time-based patterns of activities, e.g., whether events should be on the same day or not. These are not invariant under "colour permutations" and so the "same colour" representation is no longer sufficient. The matrix variable will need to capture the assignment of events to rooms as well as periods, and hence be constrained so that there is only a single event in each room-period pair. This gives a constraint on the rank of the matrix variable, which can be relaxed in a SDP. Despite the higher dimension of such relaxations, relaxations of rank-minimisation have proven very successful in many other fields (Fazel et al., 2004), and may turn out to be applicable also in timetabling. Modelling further and progressively more complex problems in semidefinite programming, with particular focus on relaxations one can solve fast, offers ample space for future work.
In theory, one may wonder whether the relaxations as the best one can obtain in polynomial time assuming the unique games conjecture (Khot, 2005). One could also seek approximation results for the problems we describe, either for the relaxations and rounding procedures of this paper, or for novel ones. For example, one could obtain socalled lifted relaxations, e.g., using the method of moments of (Lasserre, 2015) applied to the copositive formulation, and to analyse the rounding therein, as (Bansal et al., 2016) have done for job-shop scheduling. These would be an important advances in our understanding of scheduling and timetabling.