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 K-v 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 ingredients 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 Oberwolfach Problem, which is 22 times greater than those solved in previous contributions.