A new lower bound for curriculum-based course timetabling

V. Cacchiani, A. Caprara, Roberto Roberti, P. Toth

Research output: Contribution to journalJournal articleResearchpeer-review

163 Downloads (Pure)

Abstract

In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (M), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing lip the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones). (C) 2013 Elsevier Ltd. All rights reserved.
Original languageEnglish
JournalComputers & Operations Research
Volume40
Issue number10
Pages (from-to)2466-2477
Number of pages12
ISSN0305-0548
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • COMPUTER
  • ENGINEERING,
  • OPERATIONS
  • Timetabling
  • Column generation
  • Lower bounds
  • Curricula
  • Integer programming
  • Optimization
  • Scheduling
  • Course timetabling
  • Heuristic solutions
  • Integer linear programs
  • Objective functions
  • University course
  • TIME perspective

Cite this

Cacchiani, V. ; Caprara, A. ; Roberti, Roberto ; Toth, P. / A new lower bound for curriculum-based course timetabling. In: Computers & Operations Research. 2013 ; Vol. 40, No. 10. pp. 2466-2477.
@article{db25511c55e04594ac550e9d69f9ffc2,
title = "A new lower bound for curriculum-based course timetabling",
abstract = "In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (M), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing lip the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones). (C) 2013 Elsevier Ltd. All rights reserved.",
keywords = "COMPUTER, ENGINEERING,, OPERATIONS, Timetabling, Column generation, Lower bounds, Curricula, Integer programming, Optimization, Scheduling, Course timetabling, Heuristic solutions, Integer linear programs, Objective functions, University course, TIME perspective",
author = "V. Cacchiani and A. Caprara and Roberto Roberti and P. Toth",
year = "2013",
doi = "10.1016/j.cor.2013.02.010",
language = "English",
volume = "40",
pages = "2466--2477",
journal = "Computers & Operations Research",
issn = "0305-0548",
publisher = "Pergamon Press",
number = "10",

}

Cacchiani, V, Caprara, A, Roberti, R & Toth, P 2013, 'A new lower bound for curriculum-based course timetabling', Computers & Operations Research, vol. 40, no. 10, pp. 2466-2477. https://doi.org/10.1016/j.cor.2013.02.010

A new lower bound for curriculum-based course timetabling. / Cacchiani, V.; Caprara, A.; Roberti, Roberto; Toth, P.

In: Computers & Operations Research, Vol. 40, No. 10, 2013, p. 2466-2477.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - A new lower bound for curriculum-based course timetabling

AU - Cacchiani, V.

AU - Caprara, A.

AU - Roberti, Roberto

AU - Toth, P.

PY - 2013

Y1 - 2013

N2 - In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (M), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing lip the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones). (C) 2013 Elsevier Ltd. All rights reserved.

AB - In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (M), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing lip the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones). (C) 2013 Elsevier Ltd. All rights reserved.

KW - COMPUTER

KW - ENGINEERING,

KW - OPERATIONS

KW - Timetabling

KW - Column generation

KW - Lower bounds

KW - Curricula

KW - Integer programming

KW - Optimization

KW - Scheduling

KW - Course timetabling

KW - Heuristic solutions

KW - Integer linear programs

KW - Objective functions

KW - University course

KW - TIME perspective

U2 - 10.1016/j.cor.2013.02.010

DO - 10.1016/j.cor.2013.02.010

M3 - Journal article

VL - 40

SP - 2466

EP - 2477

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

IS - 10

ER -