Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14381
For citation please use:
Main Title: Optimal University Course Timetables and the Partial Transversal Polytope
Author(s): Lach, Gerald
Lübbecke, Marco E.
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15608
http://dx.doi.org/10.14279/depositonce-14381
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: University course timetabling is the conflict-free assignment of courses to weekly time slots and rooms subject to various hard and soft constraints. One goal is to meet as closely as possible professors" preferences. Building on an intuitive integer program (IP), we develop an exact decomposition approach which schedules courses first, and matches courses/times to rooms in a second stage. The subset of constraints which ensures a feasible room assignment defines the well-known partial transversal polytope. We describe it as a polymatroid, and thereby obtain a complete characterization of its facets. This enables us to add only strong valid inequalities to the first stage IP. In fact, for all practical purposes the number of facets is small. We present encouraging computational results on real-world and simulated timetabling data. The sizes of our optimally solvable instances (respecting all hard constraints) are the largest reported in the literature by far.
Subject(s): integer programming
partial transversal polytope
university course timetabling
Issue Date: 2007
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2007, 45
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-045-2007.pdf
Format: Adobe PDF | Size: 191.58 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.