ECOPT - Equitable Coloring Optimizer

ECOPT is a competitive cutting-edge Branch and Cut algorithm that solves the Equitable Coloring Problem in graphs.

Current features:

Two fast greedy heuristics which compute lower bounds of the equitable chromatic number

A fast greedy heuristic which computes good quality equitable colorings

TABUEQCOL: A tabu search heuristic which improves equitable colorings

A custom branching strategy

Two fast primal heuristics

A DSATUR-like enumeration algorithm

Multi-thread capabilities during branch-and-cut process (experimental, only in Linux version)

A cutting-plane algorithm which generates cuts from seven families of valid inequalities

ECOPT solves several instances from the literature (such as DIMACS instances and kneser graphs). In particular, ECOPT is able to solve inithx1.i.1 (an instance with 864 vertices and 18707 edges), will199GPIA (701 vertices and 6772 edges) and school1 (385 vertices and 19095 edges) in less than two minutes, on a standard PC desktop. If you want to know the performance of ECOPT in other instances, you may see it in page 103 of my thesis.
ECOPT is licensed under GNU GPL. You can download it from the following link:

ecopt.zip

ECOPT reads graphs in DIMACS COL format. Also, ECOPT requires CPLEX 12 Commercial/Academic Edition. If you compiled ECOPT with CPLEX Teaching Edition, TABUEQCOL and the enumeration algorithm would still work but the branch-and-cut process might be compromised and, consecuently, ECOPT would not be able to solve large instances. Under Windows, ECOPT also requires Visual Studio 2010 Express edition or higher.

Talks:

A polyhedral approach for the graph equitable coloring problem. VI ALIO/EURO Workshop on Applied Combinatorial Optimization. FCEyN-UBA, Buenos Aires, Argentina. December 2008. Slides.

Estudio Poliedral del Problema de Coloreo Equitativo (slides). Seminario Red Latinoamericana Prosul - Opt. discreta y grafos. UNGS, Buenos Aires, Argentina. May 2009.

Nuevas facetas del Poliedro de Coloreo Equitativo (communication). LIX Reunión Anual de Comunicaciones Científicas de la UMA. UNMP, Mar del Plata, Argentina. September 2009. Slides.

A Linear Integer Approach for the Equitable Coloring Problem. II Congreso de Matemática Aplicada, Computacional e Industrial. Univ. Austral, Rosario, Argentina. December 2009. Slides.

A Branch and Cut Algorithm for the Equitable Graph Coloring Problem (slides). ALIO-INFORMS Joint International Meeting. Fac. de Derecho de la UBA, Buenos Aires, Argentina. June 2010.

Polyhedral results for the Equitable Coloring Problem. VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2011). H. Edelweiss, Bariloche, Argentina. March 2011. Slides.

Un algoritmo exacto para el Problema de Coloreo Equitativo en Grafos. IV Congreso Latinoamericano de Matemáticos (CLAM 2012). Universidad de Córdoba, Argentina. August 2012. Slides.

An Exact DSatur-based algorithm for the Equitable Coloring Problem. VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2013). H. BlueBay Grand Esmerald, Playa del Cármen, México. April 2013. Slides.

Please feel free to contact me if you have any comments, suggestions, or you find a bug in the program. My e-mail address appears in any of my publications.

(back)