Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem

DOI10.1007/978-3-319-59776-8_29zbMATH Open1489.68255OpenAlexW2618773733MaRDI QIDQ2011610FDOQ2011610

Authors: Maël Minot, Samba Ndojh Ndiaye, Christine Solnon 

Publication date: 4 August 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-59776-8_29

Recommendations

• ILP models and column generation for the minimum sum coloring problem
• A tabu search approach for the sum coloring problem
• New algorithm for the sum coloring problem
• A branch-and-price algorithm for the minimum sum coloring problem
• A memetic algorithm for the minimum sum coloring problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorics in computer science (68R05) Integer programming (90C10)

Cites Work

• SATzilla: portfolio-based algorithm selection for SAT
• Graph minors. II. Algorithmic aspects of tree-width
• Algorithm portfolios
• Graph Colorings
• A memetic algorithm for the minimum sum coloring problem
• Hybrid evolutionary search for the minimum sum coloring problem of graphs
• An effective heuristic algorithm for sum coloring of graphs
• Lower bounds for the minimal sum coloring problem
• Hybrid backtracking bounded by tree-decomposition of constraint networks
• Tight bounds on the chromatic sum of a connected graph
• An \(O(n\log n)\) bound consistency algorithm for the conjunction of an \textit{alldifferent} and an inequality between a sum of variables and a constant, and its generalization

Cited In (1)

• ILP models and column generation for the minimum sum coloring problem

Uses Software

• CPLEX
• Choco
• Gecode
• SATzilla
• llama

This page was built for publication: Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011610)