Merging combinatorial design and optimization: The oberwolfach problem

The Oberwolfach Problem OP (F) — posed by Gerhard Ringel in 1967 — is a paradigmatic Combinatorial Design problem asking whether the complete graph Kv decomposes into edge-disjoint copies of a 2-regular graph F of order v. In this paper we provide all the necessary equipment to generate solutions to OP (F) for relatively small orders by using so-called difference methods. From the theoretical standpoint, we present new insights on the combinatorial structures involved in the solution of the problem. Computationally, we provide a full recipe whose base ingre-dients are advanced optimization models and tailored algorithms. This algorithmic arsenal can solve the OP (F) for all possible orders up to 60 with the modest computing resources of a personal computer. The 20 new orders, from 41 to 60, encompass 241 200 instances of the Oberwol-fach Problem, which is 22 times greater than those solved in previous contributions.