Optimization Online


The Balanced Academic Curriculum Problem Revisited

Marco Chiarandini(marco***at***imada.sdu.dk)
Luca Di Gaspero(l.digaspero***at***uniud.it)
Stefano Gualandi(stefano.gualandi***at***polimi.it)
Andrea Schaerf(schaerf***at***uniud.it)

Abstract: The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by the universities. In this article, we introduce a generalized version of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem instances arisen at University of Udine. Since the existing formulation based on a min-max objective function does not balance effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented, and analyzed heuristics based on local search. We have solved all the new instances with the proposed approach and assessed the quality of solutions with respect to lower bounds found by ILP on a relaxed and decomposed problem. Results show that a selected heuristic finds solutions of very good quality at 9%-60% distance from the lower bound. We make all data publicly available, in order to stimulate further research on this problem.

Keywords: Combinatorial optimization; Metaheuristic Methodologies; Timetabling; Local Search

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

Category 2: Combinatorial Optimization (Meta Heuristics )


Download: [Postscript]

Entry Submitted: 12/29/2009
Entry Accepted: 12/29/2009
Entry Last Modified: 12/29/2009

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