A branch-and-cut procedure for the Udine course timetabling problem

DOI10.1007/s10479-010-0828-5zbMath1251.90276OpenAlexW2010360426WikidataQ57968679 ScholiaQ57968679MaRDI QIDQ1761891

Andrew J. Parkes, Jakub Mareček, Edmund Kieran Burke

Publication date: 15 November 2012

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-010-0828-5

zbMATH Keywords

integer programmingcutting planesbranch-and-cuteducational timetablinguniversity course timetablingsoft constraints

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)

Related Items

Fairness in academic course timetabling ⋮ Adaptive tabu search for course timetabling ⋮ Operational research in education ⋮ A new lower bound for curriculum-based course timetabling ⋮ Benders decomposition for curriculum-based course timetabling ⋮ Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem ⋮ An ILP based heuristic for a generalization of the post-enrollment course timetabling problem ⋮ An exact algorithm for the edge coloring by total labeling problem ⋮ The maximum-impact coloring polytope ⋮ Integer programming ensemble of temporal relations classifiers ⋮ The generalized balanced academic curriculum problem with heterogeneous classes ⋮ Timetable construction: the algorithms and complexity perspective ⋮ \textit{teaspoon}: solving the curriculum-based course timetabling problems with answer set programming ⋮ Preprocessing and an improved MIP model for examination timetabling ⋮ Answer set programming as a modeling language for course timetabling ⋮ Unnamed Item ⋮ Dantzig-Wolfe decomposition of the daily course pattern formulation for curriculum-based course timetabling ⋮ Preprocessing and cutting planes with conflict graphs ⋮ Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem ⋮ Flow formulations for curriculum-based course timetabling ⋮ Facet-generating procedures for the maximum-impact coloring polytope ⋮ Facet-generating procedures for the maximum-impact coloring polytope ⋮ Optimized planning of nursing curricula in dual vocational schools focusing on the German health care system ⋮ An overview of curriculum-based course timetabling

Uses Software

• CPLEX
• Cliquer

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A supernodal formulation of vertex colouring with applications in course timetabling
• The worst-case time complexity for generating all maximal cliques and computational experiments
• A mixed-integer programming approach to a class timetabling problem: a case study with gender policies and traffic considerations
• A computational study of a cutting plane algorithm for university course timetabling
• Application of a real-world university-course timetabling model solved by integer programming
• Cliques, holes and the vertex coloring polytope
• Decomposition, reformulation, and diving in university course timetabling
• Brick decompositions and the matching rank of graphs
• Properties of some ILP formulations of a class of partitioning problems
• An integer programming formulation for a case study in university timetabling.
• An automated university course timetabling system developed in a distributed environment: a case study.
• On unions and dominants of polytopes
• Recent research directions in automated timetabling
• Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and results
• Curriculum based course timetabling: new solutions to Udine benchmark instances
• Linear-time separation algorithms for the three-index assignment polytope
• Facets of the graph coloring polytope
• Efficient solutions for a university timetabling problem through integer programming
• ITC2007 solver description: a hybrid approach
• Facets of the three-index assignment polytope
• A computational approach to enhancing course timetabling with integer programming
• A cutting plane algorithm for graph coloring
• A branch-and-cut algorithm for graph coloring
• Neighborhood portfolio approach for local search applied to timetabling problems
• Edmonds polytopes and a hierarchy of combinatorial problems
• Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition
• School Timetabling—A Case in Large Binary Integer Linear Programming
• Towards improving the utilization of university teaching space
• A Lagrangian Relaxation Approach To The Classroom Assignment Problem^*
• An Algorithm for the Three-Index Assignment Problem
• Penalising Patterns in Timetables: Novel Integer Programming Formulations
• Maximum matching and a polyhedron with 0,1-vertices
• An upper bound for the chromatic number of a graph and its application to timetabling problems

This page was built for publication: A branch-and-cut procedure for the Udine course timetabling problem