## Contributed Session Wed.3.H 3005

#### Wednesday, 15:15 - 16:45 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Graph coloring

**Chair: Jakub Marecek**

**Wednesday, 15:15 - 15:40 h, Room: H 3005, Talk 1**

**Noriyoshi Sukegawa**

Lagrangian relaxation and pegging test for clique partitioning problems

**Coauthors: Yoshitsugu Yamamoto, Liyuan Zhang**

**Abstract:**

We develop a relaxation method to solve the clique partitioning problem (CPP), as it is done customarily by the Lagrangian relaxation, but in a new approach we have aimed at overcoming the burden imposed by the number of constraints. Since the binary integer linear programming formulation of CPP has a huge number of inequality constraints, we propose a modified Lagrangian relaxation which discards some of the multipliers and the modified subgradient method to solve the Lagrangain dual problem defined by the modified Lagrangian relaxation. This modification enables us to apply the Lagrangian relaxation to large instances. Computational results show that only a small fraction of all constraints are considered eventually. We also propose an improvement of the ordinary pegging test by using the structural property of CPP. The pegging test reduces the size of given instances, often significantly, and contributes to finding a very tight upper bound for several instances.

**Wednesday, 15:45 - 16:10 h, Room: H 3005, Talk 2**

**Marcin Jurkiewicz**

Colorings of the strong product of graphs

**Abstract:**

Graph coloring is one of the famous problems in graph theory and it has many applications. We present algorithms for coloring strong product of graphs. We also show their applications to bounding the Witsenhausen's rate. The rate is strongly related to the chromatic number of some graph products and it measures the smallest number of possible messages the informant must transmit in the zero-error source coding problem with side-information.

**Wednesday, 16:15 - 16:40 h, Room: H 3005, Talk 3**

**Jakub Marecek**

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

**Coauthor: Andrew J. Parkes**

**Abstract:**

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.