A Branch-and-cut Procedure for the Udine Course Timetabling Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00058937" target="_blank" >RIV/00216224:14330/12:00058937 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s10479-010-0828-5" target="_blank" >http://dx.doi.org/10.1007/s10479-010-0828-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10479-010-0828-5" target="_blank" >10.1007/s10479-010-0828-5</a>

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

Abstract A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem. A number of further classes of cuts are also introduced, arising from: enumeration of event/free-period patterns; bounds on the numbers of days of instruction; the desire to exploit integrality of the objective function value; the graph colouring component; and also from various implied bounds.

Název v anglickém jazyce

A Branch-and-cut Procedure for the Udine Course Timetabling Problem

Popis výsledku anglicky

Abstract A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem. A number of further classes of cuts are also introduced, arising from: enumeration of event/free-period patterns; bounds on the numbers of days of instruction; the desire to exploit integrality of the objective function value; the graph colouring component; and also from various implied bounds.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2012

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ů

Název periodika

Annals of Operations Research

ISSN

0254-5330

e-ISSN

—

Svazek periodika

194

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

17

Strana od-do

71-87

Kód UT WoS článku

000300574500005

EID výsledku v databázi Scopus

—