Solving the n -Fractions Puzzle Using Integer Programming

We present a teaching case study in which we solve the n-fractions puzzle using a Mixed Integer Programming model. The n-fractions puzzle is problem 41 in CSPLib, a library of test problems for Constraint Programming solvers. We first propose a model which is correct assuming exact arithmetic and show how to modify the model to account for floating point rounding errors. We then reuse ideas from constraint programming approaches to the puzzle and limit the lowest common multiple (LCM) of the denominators in the solution. This massively reduces solution time and means we can finally close the remaining open case to the puzzle. The apparent simplicity of the puzzle, the novelty of the modelling techniques used and the speedups achieved through limiting the LCM make the puzzle an interesting teaching case study. Funding: This work was supported by the Australian Government (RTP Scholarship).