Solving the Greek school timetabling problem by a mixed integer programming model

Abstract

This study deals with the school timetabling problem for the case of Greek high schools. At first, the problem is modelled as a Mixed Integer Programming problem for ten instances referring to Greek high schools. Then, the problem is coded using the MathProg programming language. Two different linear programming solvers are employed, Gurobi and CPLEX, to solve the problem for the instances at hand. Two methodologies are proposed. The first one deals with the problem utilising a model that includes all hard and soft constraints, called “monolithic” model, while the second one is based on a decomposition of the problem to six sub-problems. It should be stated that Gurobi and CPLEX did not produced satisfactory results when the monolithic model was the case. Computational results demonstrate the effectiveness of the second proposed methodology, as optimal solutions or new lower bounds were found. In addition, the results produced by Mixed Integer Programming are compared with the best so far published results, obtained by two Nature Inspired algorithms namely Particle Swarm Optimization and Cat Swarm Optimization.

Keywords:

• School timetabling
• mixed integer programming
• linear programming solvers
• mathprog programming language

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 MathProg | http://lpsolve.sourceforge.net/5.5/MathProg.htm

2 AMPL | http://ampl.com/

3 Gurobi Optimization | http://www.gurobi.com/

4 IBM CPLEX Optimizer | https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

5 http://www.deapt.upatras.gr/school_timetabling_MIP_modeling

6 http://www.deapt.upatras.gr.school_timetabling_MIP_modeling/ [University of Patras, Greece]