Formulazioni dei problemi di colorazione¶
Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 11 · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di colorazione
Prerequisiti
-
Dal modulo Programmazione lineare, Capitolo 9 «Teoria della dualità»: il duale di un problema LP, dualità debole e forte.
-
Dal modulo Programmazione lineare intera, Capitolo 1 «Programmazione lineare intera» e Capitolo 2 «Bound primali e duali»: problemi PLI, rilassamenti lineari e bound.
-
Da questo modulo, Capitolo 4 «Problemi di colorazione»: il problema, le sue ipotesi e la notazione sui grafi.
Obiettivi
Al termine di questo capitolo saremo in grado di:
-
scrivere il modello PLI del problema della colorazione dei vertici e spiegare il ruolo delle variabili di attivazione \(y_c\);
-
scrivere i due rilassamenti lineari e i loro duali, e calcolarne le soluzioni ottime;
-
dimostrare che il valore ottimo dei rilassamenti lineari è \(2\) per ogni grafo con almeno uno spigolo;
-
spiegare perché questo bound è molto debole, e perché il modello non basta per colorare un grafo.
11.1 Panoramica della famiglia¶
-
I modelli PLI dei problemi di colorazione usano un upper bound \(k\) sul numero di colori e l'insieme \(\mathscr{C} = \{1,2,\dots,k\}\) dei colori che si possono usare.
-
Le variabili di assegnamento binarie \(x_{vc}\) danno un colore \(c \in \mathscr{C}\) a ogni vertice \(v \in V\), e le variabili di attivazione binarie \(y_c\) dicono se il colore \(c\) è usato.
-
Ogni spigolo e ogni colore danno un vincolo, che vieta lo stesso colore sui due estremi dello spigolo, e la funzione obiettivo minimizza il numero \(\sum_{c \in \mathscr{C}} y_c\) di colori usati.
I modelli di colorazione sono modelli di assegnamento, come i modelli di packing: un vertice è assegnato a un colore come un oggetto è assegnato a un contenitore, e i vincoli sugli spigoli prendono il posto dei vincoli di capacità.
- La tabella elenca i membri della famiglia, con il nome del loro modello PLI e la sezione che lo scrive.
| Problema | Modello | Variabili | Sezione |
|---|---|---|---|
| VCP | \(\mathrm{ILP}_{\mathrm{VCP}}\) | binarie \(x_{vc}\) e \(y_c\) | 11.2 |
Avanti: 11.2 Un modello PLI per il problema della colorazione dei vertici
Esercizi su questo capitolo: Problemi di colorazione