A supernodal formulation of vertex colouring with applications in course timetabling
From MaRDI portal
Publication:610967
DOI10.1007/S10479-010-0716-ZzbMATH Open1207.05046arXiv0710.3603OpenAlexW2087215158WikidataQ57968710 ScholiaQ57968710MaRDI QIDQ610967FDOQ610967
Authors: Jakub Mareček, Andrew J. Parkes, Hana Rudová, Edmund K. Burke 
Publication date: 13 December 2010
Published in: Annals of Operations Research (Search for Journal in Brave)
Abstract: Vertex colouring is a well-known problem in combinatorial optimisation, whose alternative integer programming formulations have recently attracted considerable attention. This paper briefly surveys seven known formulations of vertex colouring and introduces a formulation of vertex colouring using a suitable clique partition of the graph. This formulation is applicable in timetabling applications, where such a clique partition of the conflict graph is given implicitly. In contrast with some alternatives, the presented formulation can also be easily extended to accommodate complex performance indicators (``soft constraints) imposed in a number of real-life course timetabling applications. Its performance depends on the quality of the clique partition, but encouraging empirical results for the Udine Course Timetabling problem are reported.
Full work available at URL: https://arxiv.org/abs/0710.3603
Recommendations
Cites Work
- Title not available (Why is that?)
- A survey of local search methods for graph coloring
- Title not available (Why is that?)
- On the system of two all different\(\_\)predicates
- Graph derivatives
- Conflict analysis in mixed integer programming
- Random graphs.
- Representations of the all\_different predicate of constraint satisfaction in integer programming
- Linear degree extractors and the inapproximability of max clique and chromatic number
- The strong perfect graph theorem
- Handbook of Graph Theory
- Transitiv orientierbare Graphen
- The two possible values of the chromatic number of a random graph
- Recent research directions in automated timetabling
- Facets of the graph coloring polytope
- 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
- What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
- A computational study of a cutting plane algorithm for university course timetabling
- Packing and partitioning orbitopes
- A Combinatorial Decomposition Theory
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- The complexity of comparability graph recognition and coloring
- Properties of some ILP formulations of a class of partitioning problems
- On the asymmetric representatives formulation for the vertex coloring problem
- Generating all the acyclic orientations of an undirected graph
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Incremental modular decomposition
- A Column Generation Approach for Graph Coloring
- Nombre chromatique et plus longs chemins d'un graphe
- On the X-join decomposition for undirected graphs
- Towards improving the utilization of university teaching space
- Application of a real-world university-course timetabling model solved by integer programming
- Zero knowledge and the chromatic number
- Title not available (Why is that?)
- Models and solution techniques for frequency assignment problems
- A class representative model for pure parsimony haplotyping
- The Complexity of Near-Optimal Graph Coloring
- Cliques, holes and the vertex coloring polytope
- Pruning by isomorphism in branch-and-cut
- Exploiting orbits in symmetric ILP
- Symmetric ILP: Coloring and small integers
- Orbitopal Fixing
- A dualistic approach to bounding the chromatic number of a graph
- Weighted graphs and university course timetabling
- Penalising patterns in timetables: novel integer programming formulations
- Two novel evolutionary formulations of the graph coloring problem
- All-different polytopes
- On a binary-encoded ILP coloring formulation
- Using stable sets to bound the chromatic number
- On the Application of the Minimum Degree Algorithm to Finite Element Systems
- Title not available (Why is that?)
- Orbital Branching
Cited In (27)
- Fractional programming formulation for the vertex coloring problem
- Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling
- \textit{teaspoon}: solving the curriculum-based course timetabling problems with answer set programming
- An overview of curriculum-based course timetabling
- SAT-boosted tabu search for coloring massive graphs
- Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem
- An integer programming approach to b-coloring
- Polyhedral studies of vertex coloring problems: the standard formulation
- Comments on: ``An overview of curriculum-based course timetabling
- Operational research in education
- Variable neighborhood descent search based algorithms for course timetabling problem: application to a Tunisian university
- A branch-and-cut procedure for the Udine course timetabling problem
- Dantzig-Wolfe decomposition of the daily course pattern formulation for curriculum-based course timetabling
- The maximum-impact coloring polytope
- A new lower bound for curriculum-based course timetabling
- Minimum penalty perturbation heuristics for curriculum-based timetables subject to multiple disruptions
- Generating new test instances by evolving in instance space
- Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem
- Answer set programming as a modeling language for course timetabling
- Grouping products for the optimization of production processes: a case in the steel manufacturing industry
- The minimum chromatic violation problem: a polyhedral approach
- Split Vertices in Vertex Colouring and Their Application in Developing a Solution to the Faculty Timetable Problem
- Mobility offer allocations in corporate settings
- Symmetry-breaking inequalities for ILP with structured sub-symmetry
- Quality recovering of university timetables
- A column generation based algorithm for the robust graph coloring problem
- Multi-coloring and job-scheduling with assignment and incompatibility costs
Uses Software
This page was built for publication: A supernodal formulation of vertex colouring with applications in course timetabling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q610967)
