Formulazioni dei problemi di clique¶
Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 12 · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di clique
Prerequisiti
-
Da questo modulo, Capitolo 5 «Problemi di clique»: il problema, le sue ipotesi, clique, insiemi stabili, il grafo complementare e \(\omega(G)=\alpha(\overline{G})\).
-
Da questo modulo, Capitolo 4 «Problemi di colorazione» e Capitolo 11 «Formulazioni dei problemi di colorazione»: il numero cromatico \(\chi(G)\) e un modello PLI con i suoi rilassamenti lineari.
-
Dal modulo Programmazione lineare intera, Capitolo 2 «Bound primali e duali», Capitolo 3 «Formulazioni ideali» e Capitolo 4 «Disuguaglianze valide»: rilassamenti lineari, formulazioni più forti e disuguaglianze valide.
-
Dal modulo Programmazione lineare, Capitolo 9 «Teoria della dualità»: il duale di un problema LP, la dualità debole e la dualità forte.
Obiettivi
Al termine di questo capitolo saremo in grado di:
-
scrivere la formulazione sugli spigoli del problema della clique massima sui non-spigoli di \(G\), cioè sugli spigoli di \(\overline{G}\);
-
spiegare perché il suo rilassamento lineare è debole: il punto \(x_v=\tfrac{1}{2}\) è sempre ammissibile;
-
scrivere la formulazione a clique e confrontare i due bound LP su un grafo piccolo;
-
dimostrare \(\omega(G)\le z(\mathrm{LP}^{\mathrm{CL}}_{\mathrm{MCP}})\le\chi(G)\) con la dualità LP e una formulazione di colorazione;
-
scrivere la formulazione sugli spigoli e la formulazione a clique del problema dell'insieme stabile massimo;
-
scrivere i modelli PLI dei problemi della clique massima pesata sui vertici e pesata sugli spigoli, linearizzando il prodotto \(x_u\,x_v\) con le variabili \(y_{uv}\).
12.1 Panoramica della famiglia¶
-
I modelli PLI dei problemi di clique usano una variabile binaria di selezione \(x_v\) per ogni vertice \(v \in V\), pari a \(1\) se il vertice è nella clique.
-
Due vertici non adiacenti non possono essere selezionati entrambi: i vincoli di conflitto si scrivono sui non-spigoli di \(G\), cioè sugli spigoli del grafo complementare \(\overline{G}\), oppure sulle sue clique.
-
La funzione obiettivo massimizza il numero di vertici selezionati o il loro peso totale; il problema pesato sugli spigoli aggiunge una variabile per spigolo.
I modelli di clique selezionano vertici con variabili binarie e vietano la selezione di due vertici non adiacenti. Gli stessi modelli, scritti sugli spigoli di \(G\) invece che di \(\overline{G}\), selezionano insiemi stabili.
- La tabella elenca i membri della famiglia, con il nome dei loro modelli PLI e le sezioni che li scrivono.
| Problema | Modelli | Vincoli di conflitto | Sezione |
|---|---|---|---|
| MCP | \(\mathrm{ILP}_{\mathrm{MCP}}\) (formulazione sugli spigoli) | sui non-spigoli di \(G\) | 12.2 |
| MCP | \(\mathrm{ILP}^{\mathrm{CL}}_{\mathrm{MCP}}\) (formulazione a clique) | sugli insiemi stabili massimali di \(G\) | 12.5 |
| MSSP | \(\mathrm{ILP}_{\mathrm{MSSP}}\), \(\mathrm{ILP}^{\mathrm{CL}}_{\mathrm{MSSP}}\) | sugli spigoli e sulle clique di \(G\) | 12.7 |
| VWMCP | \(\mathrm{ILP}^{\mathrm{VW}}_{\mathrm{MCP}}\) | sui non-spigoli di \(G\) | 12.8 |
| EWMCP | \(\mathrm{ILP}^{\mathrm{EW}}_{\mathrm{MCP}}\) | sui non-spigoli di \(G\) | 12.8 |
-
Panoramica
Panoramica della famiglia
-
12.2 Un modello PLI per il problema della clique massima: la formulazione sugli spigoli
Un secondo rilassamento lineare · Disuguaglianze di clique: una formulazione più forte · La relazione con la colorazione dei vertici · Insiemi stabili sul grafo complementare
-
12.8 Modelli PLI per le varianti pesate
Il problema della clique massima pesata sugli spigoli · Errori tipici · In sintesi
Avanti: 12.2 Un modello PLI per il problema della clique massima: la formulazione sugli spigoli
Esercizi su questo capitolo: Problemi di clique