Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00041526" target="_blank" >RIV/00216224:14330/07:00041526 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables

Popis výsledku v původní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.

Název v anglickém jazyce

Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables

Popis výsledku anglicky

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.

Druh

O - Ostatní výsledky

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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ů