Il problema della colorazione dei grafi soluzioni esatte ed euristiche

Il problema della colorazione dei grafi soluzioni esatte ed euristiche

Esplorare il problema classico di ottimizzazione discreta attraverso euristiche costruttive personalizzate e programmazione intera in Python

La teoria della colorazione dei grafi occupa una posizione centrale nella matematica discreta. Appare in molti contesti senza apparente connessione con la colorazione. Affronta il problema fondamentale di partizionare un insieme di oggetti in classi, secondo determinate regole (Jensen & Toft, 1995).

Possiamo riassumere il problema come segue: dato un grafo non orientato G(V, E), assegnare colori ad ogni nodo (vertice) in modo che due nodi adiacenti non condividano lo stesso colore e il numero di colori utilizzati sia minimizzato. Nonostante l’affermazione concisa e chiara, questo problema è noto per la sua complessità computazionale, rientrando nella categoria dei problemi NP-hard.

A causa della sua complessità combinatoria, l’approccio esatto della Programmazione Lineare Intera (ILP) potrebbe non essere in grado di risolvere istanze di grandi dimensioni, anche quando si utilizzano i migliori risolutivi disponibili. In tali situazioni, euristiche e metaeuristiche possono essere interessanti alternative. Sebbene non siano in grado di provare l’ottimalità, questi metodi possono fornire soluzioni rapide e di buona qualità.

In questo articolo, risolveremo il Problema della Colorazione del Grafo utilizzando l’euristica costruttiva DSatur (Brélaz, 1979) e un modello di programmazione lineare intera utilizzando pyomo (Bynum et al., 2021) con il solutore HiGHS. Come per le altre storie, è possibile trovare il codice completo nel mio repository del codice.

• Comprendere la manutenzione predittiva – Radici unitarie e stazionarietà
• AdCreative.ai Review Il miglior strumento di marketing AI per gli annunci?
• Utilizzare l’apprendimento automatico nella gestione dei dati

Nel caso in cui non siate ancora familiari con la Programmazione Lineare, vi consiglio di leggere il mio articolo precedente per acquisire conoscenze fondamentali prima di procedere.

Programmazione Lineare: Teoria e Applicazioni

Concetti principali dell’ottimizzazione lineare e implementazione in Python

towardsdatascience.com

Ora mettiamoci all’opera per creare soluzioni sorprendenti come questa.

Euristica costruttiva – DSatur

Ricordiamo la definizione del nostro problema:

• Consideriamo un grafo non orientato G(V, E).
• Assegnamo colori ad ogni nodo in modo che due nodi adiacenti non condividano lo stesso colore.
• Minimizziamo il numero di colori utilizzati.

Una soluzione euristica ingenua può consistere nel scegliere successivamente un nodo vuoto e assegnargli un colore, assicurandosi che questo colore non sia già stato utilizzato nei suoi vicini. Questo potrebbe non essere la migliore strategia possibile, ma sicuramente può fornire un limite superiore per il numero necessario di colori. Tuttavia, l’algoritmo DSatur (Brélaz, 1979) include nuovi elementi per la scelta del nodo successivo e per il miglioramento di questa euristica.

• Grado: Numero di archi collegati a un dato nodo.
• Saturazione: Numero di colori diversi utilizzati nei nodi adiacenti.

L’algoritmo per DSatur parte da una coda di nodi non colorati e sceglie iterativamente un nodo con un grado di saturazione massimale, lo rimuove dalla coda e gli assegna un colore. Se esiste una parità nella saturazione, Brélaz (1979) suggerisce di scegliere qualsiasi elemento con saturazione massima. Noi invece adotteremo un approccio leggermente diverso, rompendo gli eventuali legami scegliendo il nodo con il grado complessivo massimale. Il colore assegnato a un dato nodo dovrebbe essere quello con l’indice più basso disponibile. Un pseudocodice è presentato di seguito. Consideriamo N l’insieme dei nodi, Q la coda dei nodi non colorati che fa riferimento agli stessi indirizzi di memoria di N stesso, e C l’insieme dei colori utilizzati.

“`html

dsatur(N)  Q = [&n for n in N]  C = {}  while |Q| > 0:    sort(Q) // descending order by saturation and degree    n = Q.pop(0)    assign_color(n, C)

La funzione assign_color dovrebbe verificare il colore disponibile con l’indice più basso e, se nessuno dell’insieme corrente è fattibile, includere una nuova alternativa e incrementare l’insieme.

Ora mettiamo tutto questo nel codice Python. Iniziamo con l’importazione dei pacchetti. La nostra euristica sarà scritta in Python puro con solo alcune importazioni di tipo.

from typing import List, Tuple

Ora, definiamo i nostri elementi di base del modello: Colori e Nodi. La classe Color viene definita come segnaposto modificabile per gli indici corrispondenti delle loro istanze. Questo può essere efficiente in termini di memoria in Python poiché più variabili possono fare riferimento alla stessa posizione di memoria. Il metodo add_node dovrebbe essere chiamato ogni volta che un nuovo nodo viene colorato con un colore specifico.

class Color:    index: int    n_nodes: int    def __init__(self, index) -> None:        self.index = index        self.n_nodes = 0    def __repr__(self):        return f"C{self.index}"    def add_node(self):        self.n_nodes = self.n_nodes + 1

Ora la classe Node. Ogni istanza di Node ha un attributo neighbors che è una lista di nodi (puntatori). Quindi, ogni volta che un nodo viene modificato, non è necessario modificare alcuna informazione nei suoi vicini. Possiamo aggiungere un vicino utilizzando il metodo add_neighbor, impostare il suo colore utilizzando il metodo set_color, e accedere alle proprietà che dipendono dagli stati correnti dei loro vicini neighbor_colors, saturation, e degree.

class Node:    neighbors: List['Node']    index: int    color: Color    def __init__(self, index):        self.index = index        self.neighbors = []        self.color = None    def __repr__(self) -> str:        return f"N{self.index}|{self.color}"    def add_neighbor(self, node: 'Node'):        if node not in self.neighbors:            self.neighbors.append(node)    def set_color(self, color: Color):        self.color = color        color.add_node()    @property    def neighbor_colors(self):        return [n.color for n in self.neighbors if n.color is not None]    @property    def saturation(self):        return len(set((n.color for n in self.neighbors if n.color is not None)))    @property    def degree(self):        return len(self.neighbors)

Ora l’algoritmo DSatur. Per implementarlo, verrà creata una classe con lo stesso nome. La creazione di una nuova istanza di DSatur richiede come argomenti il numero di nodi n_nodes e edges del grafo. Quindi istanzia i nodi e imposta i loro vicini in base agli archi.

class DSatur:    N: List[Node]    C: List[Color]    history: List[Node]    def __init__(self, nodes: List[int], edges: List[Tuple[int, int]]):        N = [Node(i) for i in nodes]        for e in edges:            i, j = e            N[i].add_neighbor(N[j])            N[j].add_neighbor(N[i])        self.N = N        self.C = []        self.history = []    def find_next_color(self, node: Node) -> Color:        next_color = None        for c in self.C:            if c not in node.neighbor_colors:                next_color = c                break        if next_color is None:            next_color = Color(len(self.C) + 1)            self.C.append(next_color)        return next_color    def solve(self, save_history=False):        Q = [n for n in self.N]  # Pool di nodi non colorati        while len(Q) > 0:            Q.sort(key=lambda x: (x.saturation, x.degree), reverse=True)            n: Node = Q.pop(0)            next_color = self.find_next_color(n)            n.set_color(next_color)            if save_history:                self.history.append(n)        self.C.sort(key=lambda x: x.n_nodes, reverse=True)    @property    def cost(self):        return len(self.C)

“`

Ora utilizziamolo per risolvere alcuni problemi impegnativi! Puoi trovare diversi esempi nell’OR Library. Sono indicati come “gcolX” lì. Possiamo estrarre il numero di nodi e archi da uno di quei file utilizzando il seguente codice.

# Apri e leggi il filecon open($YOUR_FILE_PATH, mode="r") as file:    lines = file.readlines()    header = lines[0].strip().split()    n_nodes = int(header[2])    edges = []    node_set = set()    for line in lines[1:]:        if line.startswith('e'):            _, i, j = line.strip().split()            edges.append((int(i), int(j)))            node_set.add(int(i))            node_set.add(int(j))nodes = sorted(node_set)assert len(nodes) == n_nodes, "Numero errato di nodi specificato"

Poi semplicemente analizziamo queste istanze in una nuova istanza di DSatur e risolviamo il problema (o almeno otteniamo un’approssimazione di buona qualità).

dsatur = DSatur(nodes, edges)dsatur.solve()

Il codice per creare quella interessante visualizzazione dei risultati dall’introduzione potrebbe essere troppo verboso per essere incluso qui, ma puoi trovarlo nel mio repository di codice. Può fornire un’idea generale di quanto sia difficile gestire diversi nodi…

Ora vediamo come potremmo gestirlo con un approccio esatto.

Programmazione Lineare Intera

Per raffinare le nostre soluzioni ottenute utilizzando euristiche e cercare di dimostrare l’ottimalità delle soluzioni, formuliamo il problema della colorazione dei grafi come un modello di PLI. Ricorda che potrebbe non essere in grado di gestire istanze grandi. Il modello presentato in questa sezione e altri algoritmi esatti sono presentati nel capitolo 3 di Lewis (2021).

Definiamo i set considerati in questo approccio:

• C: Colori
• N: Nodi (o vertici)
• E: Archi

Una prima domanda sorge spontanea “Quanti colori dovremmo considerare?”. Nel caso peggiore, tutti i nodi sono collegati, quindi si dovrebbe considerare C della stessa dimensione di N. Tuttavia, questo approccio potrebbe rendere le nostre soluzioni ancora più difficili aumentando inutilmente il numero di variabili decisionali e peggiorando il rilassamento lineare del modello. Una buona alternativa è utilizzare un metodo euristico (come DSatur) per ottenere un limite superiore per il numero di colori.

In questo problema, abbiamo due gruppi di variabili decisionali:

• x_{i, c}: Sono variabili binarie che indicano che il nodo i è colorato con c
• y_{c}: Sono variabili binarie che indicano che il colore c viene utilizzato

Dobbiamo inoltre creare vincoli per garantire che:

• Ogni nodo debba essere colorato
• Se un qualsiasi nodo di un arco ha un colore, assicura che il colore venga utilizzato
• Al massimo 1 nodo di ogni arco può essere colorato con un dato colore
• Spezzare la simmetria (questo non è obbligatorio, ma potrebbe aiutare)

Infine, il nostro obiettivo dovrebbe essere minimizzare il numero totale di colori utilizzati, che è la somma di y. Riassumendo abbiamo le seguenti equazioni.

Senza ulteriori indugi, importiamo pyomo per il modello di programmazione lineare intera.

import pyomo.environ as pyo

Ci sono due approcci per modellare un problema in pyomo: modelli astratti e concreti. Nel primo approccio, le espressioni algebriche del problema vengono definite prima che vengano forniti alcuni valori dei dati, mentre nel secondo l’istanza del modello viene creata immediatamente mentre i suoi elementi vengono definiti. Puoi trovare ulteriori informazioni su questi approcci nella documentazione della libreria o nel libro di Bynum et al. (2021). In tutto questo articolo adotteremo la formulazione del modello concreto.

model = pyo.ConcreteModel()

Quindi, istanziamo i nostri Set. L’analisi degli iterabili direttamente dagli attributi N e C di dsatur è valida, quindi potremmo usarli negli argomenti di inizializzazione initialize. In alternativa, passerò i nodi e gli archi originali dai nostri dati di input e creerò un intervallo dal DSatur come inizializzazione per i colori.

model.C = pyo.Set(initialize=range(len(dsatur.C)))  # Colori
model.N = pyo.Set(initialize=nodes)  # Nodi
model.E = pyo.Set(initialize=edges])  # Archi

Successivamente, istanziamo le nostre variabili decisionali.

model.x = pyo.Var(model.N, model.C, within=pyo.Binary)
model.y = pyo.Var(model.C, within=pyo.Binary)

E poi le nostre restrizioni.

# Riempire ogni nodo con un colore
def fill_cstr(model, i):
    return sum(model.x[i, :]) == 1

# Non ripetere i colori sugli archi e indicare che il colore è usato
def edge_cstr(model, i, j, c):
    return model.x[i, c] + model.x[j, c] <= model.y[c]

# Rompere la simmetria impostando un ordine di preferenza (non richiesto)
def break_symmetry(model, c):
    if model.C.first() == c:
        return 0 <= model.y[c]
    else:
        c_prev = model.C.prev(c)
        return model.y[c] <= model.y[c_prev]

model.fill_cstr = pyo.Constraint(model.N, rule=fill_cstr)
model.edge_cstr = pyo.Constraint(model.E, model.C, rule=edge_cstr)
model.break_symmetry = pyo.Constraint(model.C, rule=break_symmetry)

Puoi provare ad includere altre restrizioni per rompere la simmetria e vedere quale funziona meglio con il tuo risolutore disponibile. In alcuni esperimenti che ho condotto, includere un ordine di preferenza utilizzando il numero totale di nodi assegnati a un determinato colore è stato peggio che ignorarlo. Probabilmente a causa delle strategie di rottura della simmetria native del risolutore.

# Rompere la simmetria impostando un ordine di preferenza con assegnazioni totali
def break_symmetry_agg(model, c):
    if model.C.first() == c:
        return 0 <= sum(model.x[:, c])
    else:
        c_prev = model.C.prev(c)
        return sum(model.x[:, c]) <= sum(model.x[:, c_prev])

Infine, l’obiettivo…

# Numero totale di colori utilizzati
def obj(model):
    return sum(model.y[:])

model.obj = pyo.Objective(rule=obj)

E il nostro modello è pronto per essere risolto! Per farlo, sto usando il solver persistente HiGHS, disponibile in pyomo nel caso in cui highspy sia installato anche nell’ambiente Python.

solver = pyo.SolverFactory("appsi_highs")
solver.highs_options["time_limit"] = 120
res = solver.solve(model)
print(res)

Per istanze grandi, il nostro risolutore potrebbe avere difficoltà nel cercare di migliorare soluzioni euristiche. Tuttavia, per un’istanza di 32 nodi disponibile nel repository del codice, il risolutore è stato in grado di ridurre il numero di colori utilizzati da 9 a 8. Vale la pena sottolineare che ha impiegato 24 secondi per completare l’esecuzione, mentre l’algoritmo DSatur per la stessa istanza ha impiegato solo 6 millisecondi (usando Python puro, che è un linguaggio interpretato).

Lettura aggiuntiva

Anche se DSatur è un’euristica intuitiva che fornisce soluzioni di buona qualità in modo rapido, altre potrebbero portare a risultati migliori, specialmente su istanze complesse. Una delle meta-euristiche più famose per il problema della colorazione dei grafi è Tabucol (Hertz & Werra, 1987). Gli autori propongono un metodo che parte da una soluzione iniziale con k colori e possibilmente archi che collegano nodi dello stesso colore. Quindi, vengono eseguiti spostamenti locali che modificano il colore di un dato nodo in modo da minimizzare le violazioni, utilizzando una Tabu List per evitare ottimi locali.

Metodi esatti più efficienti per il Problema del Colorazione del Grafo di quello presentato qui si basano su Column Generation, utilizzando un algoritmo denominato Branch & Price. Il lettore interessato a una introduzione all’argomento potrebbe trovare una panoramica concisa nella mia altra storia del VoAGI.

Column Generation nella Programmazione Lineare e il Problema di Taglio

Come risolvere problemi lineari con un gran numero di variabili decisionali illustrato con un esempio in Python

towardsdatascience.com

Conclusioni

In questo articolo sono stati presentati due approcci per risolvere il Problema del Colorazione del Grafo: l’euristica costruttiva DSatur (Brélaz, 1979) e un modello di Programmazione Lineare Interi (ILP). l’euristica è stata in grado di fornire soluzioni di buona qualità veloci per un’istanza di dimensioni moderate, di cui la soluzione è stata ulteriormente migliorata utilizzando il modello ILP. Il codice implementato è disponibile per ulteriori utilizzi in un repository pubblico.

Riferimenti

Brélaz, D., 1979. New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256.

Bynum, M. L. et al., 2021. Pyomo-optimization modeling in Python. Springer.

Hertz, A., & Werra, D. D., 1987. Using tabu search techniques for graph coloring. Computing, 39(4), 345–351.

Jensen, T. R., & Toft, B., 1995. Graph coloring problems. John Wiley & Sons.

Lewis, R.M.R., 2021. Advanced Techniques for Graph Colouring. In: Guide to Graph Colouring. Texts in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-030-81054-2_4