Talks and presentations

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.