A supernodal formulation of vertex colouring with applications in course timetabling
From MaRDI portal
(Redirected from Publication:610967)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3896181 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 3205929 (Why is no real title available?)
- scientific article; zbMATH DE number 3257176 (Why is no real title available?)
- A Column Generation Approach for Graph Coloring
- A Combinatorial Decomposition Theory
- A branch-and-cut algorithm for graph coloring
- A class representative model for pure parsimony haplotyping
- A computational study of a cutting plane algorithm for university course timetabling
- A cutting plane algorithm for graph coloring
- A dualistic approach to bounding the chromatic number of a graph
- A survey of local search methods for graph coloring
- All-different polytopes
- Application of a real-world university-course timetabling model solved by integer programming
- Cliques, holes and the vertex coloring polytope
- Conflict analysis in mixed integer programming
- Exploiting orbits in symmetric ILP
- Facets of the graph coloring polytope
- Generating all the acyclic orientations of an undirected graph
- Graph derivatives
- Handbook of Graph Theory
- Incremental modular decomposition
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Models and solution techniques for frequency assignment problems
- Neighborhood portfolio approach for local search applied to timetabling problems
- Nombre chromatique et plus longs chemins d'un graphe
- On a binary-encoded ILP coloring formulation
- On the Application of the Minimum Degree Algorithm to Finite Element Systems
- On the X-join decomposition for undirected graphs
- On the asymmetric representatives formulation for the vertex coloring problem
- On the system of two all different\(\_\)predicates
- Orbital Branching
- Orbitopal Fixing
- Packing and partitioning orbitopes
- Penalising patterns in timetables: novel integer programming formulations
- Properties of some ILP formulations of a class of partitioning problems
- Pruning by isomorphism in branch-and-cut
- Random graphs.
- Recent research directions in automated timetabling
- Representations of the all\_different predicate of constraint satisfaction in integer programming
- Symmetric ILP: Coloring and small integers
- The Complexity of Near-Optimal Graph Coloring
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- The complexity of comparability graph recognition and coloring
- The strong perfect graph theorem
- The two possible values of the chromatic number of a random graph
- Towards improving the utilization of university teaching space
- Transitiv orientierbare Graphen
- Two novel evolutionary formulations of the graph coloring problem
- Using stable sets to bound the chromatic number
- Weighted graphs and university course timetabling
- What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
- Zero knowledge and the chromatic number
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
- Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem
- SAT-boosted tabu search for coloring massive graphs
- 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
- Symmetry-breaking inequalities for ILP with structured sub-symmetry
- Mobility offer allocations in corporate settings
- 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
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)
