Talks and presentations

From Cliques to Colorings and Back Again

August 03, 2022

Talk, Constraint Programming Conference, Haifa, Israel

We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology.

Graph Coloring using Decision Diagrams with Zykov Branching

January 25, 2022

Talk, INFORMS Computing Society Conference, Tampa Bay, FL

A recent work by van Hoeve introduced a decision diagram based iterative refinement algorithm for finding multi-path solutions to optimization problems. We study the addition of branch and bound to this algorithm, including the well-known Zykov branching rule for graph coloring.

Graph Coloring With Decision Diagrams: An Analysis Of Variable Ordering

October 25, 2021

Talk, INFORMS Annual Conference, Anaheim, CA

A decision diagram approach was recently introduced to generate lower bounds for the graph coloring problem. It uses compilation via iterative refinement, which requires a variable ordering to be specified in advance. Oftentimes no single variable ordering dominates all others for a set of problem instances. This work provides an analysis and experimental evaluation of different variable ordering strategies including using portfolios of variable orderings.