Implementing cutting planes for the chromatic violation problem

DELLE DONNE, DIEGO; ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA

Viña del Mar

Conferencia; APPLIED COMBINATORIAL OPTIMIZATION 2021-2022; 2022

ALIO EURO

We consider the minimum chromatic violation problem (MCVP) studied from a polyhedral point of view. A previous paper presents the classical study of the convex hull of feasible solutions in it, introducing several exponentially sized families of valid inequalities and conditions under which they induce facets. Here we address the separation procedures for these families to find proper cuts and add them to the formulation in a cutting-plane fashion for solving the MCVP. As the inequalities analyzed in this work are associated with cliques in the given graph, we explore different clique-finding approaches and compare them xic = 1 c ∈C xic +xjc ≤ 1+zij xic +xjc ≤ 1 xic ∈ {0,1} zij ∈ {0,1} for i ∈ V, for ij ∈ F,c ∈ C, for ij ∈ E F,c ∈ C, for i ∈ V,c ∈ C, for ij ∈ F. (1) (2) (3) (4) (5) The objective function minimizes the number of (weak) edges within computational experimentation over a set of DIMACS and random instances.