| Identifikační kód | RIV/00216224:14330/12:00058937 |
|---|
| Název v anglickém jazyce | A Branch-and-cut Procedure for the Udine Course Timetabling Problem |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2012 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 2 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Edmund Burke (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska)
Jakub Mareček (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 9800964)
Andrew Parkes (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska)
Hana Rudová (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 8739781) |
|---|
| Popis výsledku v anglické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. |
|---|
| Klíčová slova oddělená středníkem | Integer programming; Branch-and-cut; Cutting planes; Soft constraints; Educational timetabling; University course timetabling |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/s10479-010-0828-5 |
|---|