A cut-and-branch algorithm for the external candidates examination scheduling problem

Twice a year, the regional school departments in Norway need to schedule examination sessions for external candidates in the region, which also involves reserving and assigning rooms, examiners and reviewers. We present a cut-and-branch algorithm to get provably good solutions to this problem, the external candidates examination scheduling problem (ExtSchedule). The algorithm relies on a new family of valid inequalities, effective in tightening the initial formulation and accelerating the solution process. We develop an efficient separation algorithm and embed it in a cut-and-branch framework to solve the problem. The algorithm has been validated on real-life instances arising from the Vestfold County school department in Norway.