Comparing Column Elimination and Column Generation


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.