ROADEF 2026>
A first exploration of the split-interval coloring polytope
Diego Delle Donne  1@  , Javier Marenco  2@  
1 : ESSEC Business School
Centre de Recherche (CERESSEC)
2 : Universidad Torcuato Di Tella
Av. Pres. Figueroa Alcorta 7350, C1428 CABA, Argentine -  Argentine

Given a graph $G=(V,E)$, a set of consecutive colors, and a demand vector $d\in\integer_+^{|V|}$, the interval coloring problem asks for an assignment of $d_i$ consecutive colors to each vertex $i\in V$, in such a way that no two adjacent vertices are assigned the same color. Inspired by a situation arising in the allocation of ships to berths, in this work we propose to consider the \emph{split-interval coloring problem}, which asks to assign at most two disjoint color intervals to each vertex in such a way that each vertex $i\in V$ receives a total of $d_i$ colors. We explore a natural integer programming formulation for this NP-hard problem and its associated polytope. We state some relations to the interval coloring polytope, including lemmas allowing to translate valid inequalities between these two polytopes. We also present several valid inequalities and study conditions ensuring that these inequalities induce facets of the associated polytope.


Chargement... Chargement...