A Branch-and-Cut Procedure for the Udine Course Timetabling Problem
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00041927" target="_blank" >RIV/00216224:14330/08:00041927 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A Branch-and-Cut Procedure for the Udine Course Timetabling Problem
Popis výsledku v původním jazyce
This paper describes a branch-and-cut procedure for a curriculum-based university course timetabling. First, we present an alternative integer programming formulation for this problem, which uses a lower than usual number of variables and a number of constraints exponential in the number of periods per day necessary to reach optimality. Second, we present a branch-and-cut procedure, where constraints from enumeration of event/free-period patterns, necessary to reaching optimality, are added only when they are violated. We also describe further problem-specific cuts from bounds implied by the soft constraints, cuts from patterns given by days of instruction and free days, and all related separation routines. We also discuss applicability of standard cuts for the graph colouring and weighted matching. The results of our preliminary experimentation with an implementation using ILOG Concert and CPLEX 10 are provided.
Název v anglickém jazyce
A Branch-and-Cut Procedure for the Udine Course Timetabling Problem
Popis výsledku anglicky
This paper describes a branch-and-cut procedure for a curriculum-based university course timetabling. First, we present an alternative integer programming formulation for this problem, which uses a lower than usual number of variables and a number of constraints exponential in the number of periods per day necessary to reach optimality. Second, we present a branch-and-cut procedure, where constraints from enumeration of event/free-period patterns, necessary to reaching optimality, are added only when they are violated. We also describe further problem-specific cuts from bounds implied by the soft constraints, cuts from patterns given by days of instruction and free days, and all related separation routines. We also discuss applicability of standard cuts for the graph colouring and weighted matching. The results of our preliminary experimentation with an implementation using ILOG Concert and CPLEX 10 are provided.
Klasifikace
Druh
O - Ostatní výsledky
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2008
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů