Anthony Karahalios

Anthony Karahalios

OR / ACO PhD Candidate at Carnegie Mellon University

Talks and presentations

Comparing Column Elimination and Column Generation

October 17, 2022

Talk, INFORMS Annual Conference, Indiannapolis, IN

A method called Column Elimination was recently introduced to generate both lower bounds and optimal solutions for the graph coloring problem. Based on dynamic programming and decision diagrams, this exact method begins with a relaxed state space and refines this space at each iteration. Our work provides methodological and computational comparisons between Column Elimination and Column Generation; it uses the Capacitated Vehicle Routing Problem (CVRP) as a case study.

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.