Per perfezionare le nostre soluzioni ottenute utilizzando l’euristica e provare a dimostrare l’ottimalità delle soluzioni, formuliamo il problema della colorazione dei grafici come modello ILP. Ricorda però che potrebbe non essere in grado di gestire istanze di grandi dimensioni. Il modello presentato in questa sezione e altri algoritmi esatti sono presentati in capitolo 3 di Lewis (2021).
Definiamo il Imposta considerati in questo approccio:
- C: Colori
- N: Nodi (o vertici)
- E: Bordi
Già sorge una prima domanda “Quanti colori dobbiamo considerare?”. Nello scenario peggiore, tutti i nodi sono collegati, quindi dovresti 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 DSatura) per ottenere un limite superiore per il numero di colori.
In questo problema abbiamo due gruppi di variabili decisionali:
- X_{io, C}: sono variabili binarie che indicano quel nodo io è colorato C
- sì_{C}: sono variabili binarie che indicano quel colore C si usa
Dobbiamo anche creare vincoli per garantire che:
- Ogni nodo deve essere colorato
- Se qualsiasi nodo di un bordo ha un colore, assicurati che il colore venga utilizzato
- Al massimo 1 nodo di ciascun bordo può essere colorato con un dato colore
- Rompi la simmetria (questo non è obbligatorio, ma potrebbe aiutare)
Infine, il nostro obiettivo dovrebbe ridurre al minimo il numero totale di colori utilizzati, che è la somma di sì. Riassumendo abbiamo le seguenti equazioni.
Senza ulteriori indugi, importiamo Piomo per il modello di programmazione intera.
import pyomo.environ as pyo
Esistono due approcci per modellare un problema Piomo: Astratto E Calcestruzzo Modelli. 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 non appena vengono definiti i suoi elementi. Puoi trovare ulteriori informazioni su questi approcci nel documentazione della biblioteca o nel libro di Bynum et al. (2021). In questo articolo adotteremo il Calcestruzzo formulazione del modello.
model = pyo.ConcreteModel()
Quindi, istanziamo il nostro Imposta. Analisi degli iterabili direttamente da dsatur attributi N E C è valido, quindi è possibile utilizzarli nel file initialize argomenti di parole chiave. In alternativa, passerò l’originale nodi E bordi dai nostri dati di input e creare un intervallo da DSatura come la nostra inizializzazione per i colori.
model.C = pyo.Set(initialize=range(len(dsatur.C))) # Colors
model.N = pyo.Set(initialize=nodes) # Nodes
model.E = pyo.Set(initialize=edges)) # Edges
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 i nostri vincoli.
# Fill every node with some color
def fill_cstr(model, i):
return sum(model.x(i, :)) == 1# Do not repeat colors on edges and indicator that color is used
def edge_cstr(model, i, j, c):
return model.x(i, c) + model.x(j, c) <= model.y(c)
# Break symmetry by setting a preference order (not required)
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 a includere altri vincoli che rompono la simmetria e vedere cosa funziona meglio con il risolutore disponibile. In alcuni esperimenti che ho eseguito, includere un ordine di preferenza utilizzando il totale dei nodi assegnati a un dato colore è stato peggiore che ignorarlo. Forse a causa delle strategie native di rottura della simmetria del risolutore.
# Break symmetry by setting a preference order with total assignments
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))
Finalmente l’obiettivo…
# Total number of colors used
def obj(model):
return sum(model.y(:))model.obj = pyo.Objective(rule=obj)
E il nostro modello è pronto per essere risolto! Per fare ciò sto utilizzando il risolutore persistente HiGHS, disponibile in Piomo nel caso altaspia è installato anche nel tuo ambiente Python.
solver = pyo.SolverFactory("appsi_highs")
solver.highs_options("time_limit") = 120
res = solver.solve(model)
print(res)
Per istanze di grandi dimensioni, il nostro risolutore potrebbe avere difficoltà a cercare di migliorare le soluzioni euristiche. Tuttavia, per un’istanza a 32 nodi disponibile nel formato deposito del codiceil risolutore è riuscito a ridurre il numero di colori utilizzati da 9 a 8. Vale la pena ricordare che ci sono voluti 24 secondi per completare l’esecuzione mentre il DSatura l’algoritmo per la stessa istanza ha richiesto solo 6 millisecondi (usando Python puro, che è un linguaggio interpretato).
Fonte: towardsdatascience.com
