Preprocessing and an improved MIP model for examination timetabling

Taha Arbaoui (), Jean-Paul Boufflet () and Aziz Moukrim ()

Annals of Operations Research, 2015, vol. 229, issue 1, 19-40

Abstract: We address the examination timetabling problem proposed in the second International Timetabling Competition (ITC2007). This paper presents new preprocessing stages and an improved mixed integer mathematical model. An exam-based conflict graph in which edges represent incompatibilities between exams is used. The preprocessing stages make use of the graph, together with hard constraints and room capacities, to reveal implicit constraints. Results show that the new preprocessing stages increase up to 106 % the number of conflict constraints an have more than doubled the size of the maximum clique. The improved mixed integer model comprises fewer constraints and is therefore more memory-efficient than the model presented after the competition. We propose valid inequalities based on cliques and a Data-dependent dual-feasible function to enhance our model. We run the tests on the twelve instances presented in the competition and the Yeditepe instances. The problem contains several criteria, which were also tested individually to help end users decide their respective importance. When our model and the original model are compared on the different instances, results show that the improved model yields better results for the majority of the cases and uses less memory. Copyright Springer Science+Business Media New York 2015

Keywords: Preprocessing; Mixed integer programming; Timetabling (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-015-1832-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:229:y:2015:i:1:p:19-40:10.1007/s10479-015-1832-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-1832-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().