Optimization Online


Computational study of a cutting plane algorithm for University Course Timetabling

Pasquale Avella (avella***at***unisannio.it)
Igor Vasil'ev (igor***at***diima.unisa.it)

Abstract: In this paper we describe a successful case-study where a Branch-and-Cut algorithm yields the \lq\lq optimal" solution of a real-world timetabling problem of University courses \emph{(University Course Timetabling problem)}. The problem is formulated as a \emph{Set Packing problem} with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing polytope, namely Clique and Lifted Odd-Hole inequalities. We also analyze the combinatorial properties of the problem to introduce new families of cutting planes that are not valid for the Set Packing polytope, and their separation algorithms. These cutting planes turned out to be very effective to yield the optimal solution of a set of real-world instances with up to $69$ courses, $59$ teachers and $15$ rooms.

Keywords: University Course Timetabling problem, Branch-and-Cut

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Journal of Scheduling 8: 497514, 2005


Entry Submitted: 07/11/2003
Entry Accepted: 07/11/2003
Entry Last Modified: 04/24/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society