Wednesday, 16:15 - 16:40 h, Room: H 3005


Jakub Marecek
Semidefinite programming relaxations in timetabling and matrix-free implementations of augmented Lagrangian methods for solving them

Coauthor: Andrew J. Parkes


Semidefinite programming provides the best known relaxations of graph colouring solvable in time polynomial in the dimensions of the graph. In order to derive strong bounds for timetabling and scheduling problems extending graph colouring, however, one cannot consider the graph colouring component alone.
We present semidefinite programming relaxations of graph colouring with an upper bound on the number of uses of each colour and numerous extensions encountered in timetabling. In timetabling terms, we consider the number of rooms available, room sizes, room features, room assignment stability, and pre-allocated room assignments.
The relaxations can be solved efficiently using alternating direction augmented Lagrangian methods (ALM). We present an ALM, which exploits the structure of the matrices involved and is essentially "matrix-free" except for a projection on the cone of positive semidefinite matrices. It can be shown the rate of convergence of ALMs within a given error bound is asymptotically the best possible, among first-order methods. The computational results suggest this may turn out to be the method of choice in practical timetabling.


Talk 3 of the contributed session Wed.3.H 3005
"Graph coloring" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. The main advantage of Viagra Soft Tablets comparing with other products of this type is its faster on-set effect.