| Identifikační kód |
RIV/00216224:14330/07:00041526 |
| Název v anglickém jazyce |
Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables |
| Druh |
O - Ostatní výsledky, které nelze zařadit do žádného z definovaných druhů výsledků |
| Jazyk |
eng - angličtina |
| Obor - skupina |
I - Informatika |
| Obor |
IN - Informatika |
| Rok uplatnění |
2007 |
| 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 |
3 |
| Počet domácích tvůrců |
2 |
| Výčet všech uvedených jednotlivých tvůrců |
Jakub Mareček (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 9800964)
Hana Rudová (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 8739781)
Edmund K. Burke (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska) |
| Popis výsledku v anglickém jazyce |
Complex real-world problems in timetabling, especially university course timetabling and employee rostering, have an underpinning graph colouring component, a pattern matching component and a number of side constraints. Problems with pattern matching constraints such as ``students should not have more than three lectures in a row and five lectures in a day'' tend to be over-constrained, making it necessary for integer programming formulations to implement pattern matching using either goal programming or to implement soft constraints, which count the number of occurrences of undesirable patterns. This paper introduces an integer programming formulation, where the number of such occurrences is counted both locally and by enumeration of patterns over daily timetables. With a number of strong valid constraints taking advantage of the interplay of the two methods of counting, this formulation seems to outperform any of its constituent parts. |
| Klíčová slova oddělená středníkem |
integer programming; course timetabling; patterns |
| Stránka www, na které se nachází výsledek |
- |
| Odkaz na údaje z výzkumu |
- |