Problema de corte máximo
O problema de corte máximo determina um subconjunto dos vértices
de um grafo, para o qual a soma dos pesos
das bordas que se cruzam de
para seus complementos
são maximizados.
Este exemplo monstra como SemidefiniteOptimization pode ser usado para configurar uma função que solucione de forma eficiente uma variante desse problema de corte máximo NP-completo.
Suponha que possui
vértices podendo ser descritos por um índice
. Use
como o vetor com componentes
para
e use
para
de modo que
é diferente de zero (=2) apenas se
e
. Assim, o corte máximo é encontrado maximizando
, onde
. O objetivo pode ser reescrito como:
... onde é a matriz laplaciana do grafo e
é a matriz de adjacência ponderada.
Para casos menores, o problema de corte máximo pode ser resolvido com exatidão, mas isso é impraticável para grafos maiores, pois, em geral, o problema tem complexidade NP-completo.
O problema minimiza , onde
é uma matriz semidefinida positiva de posto 1, com
para cada
, equivalente a
, onde
é a matriz com 1 no
posição diagonal e 0 em todo lugar.
Para tornar a solução prática, resolva um problema relaxado em que a condição de posto 1 é eliminada, para que seja necessária apenas .
O problema semidefinido na forma dupla é dado por
É resolvido usando SemidefiniteOptimization[c, {a0, a1, …, ak}, {"DualMaximizer" }].
Para a solução do problema relaxado, um corte é construído por arredondamento aleatório: decomponha
, use
como um vetor aleatório uniformemente distribuído da norma unitária e use
. Para demonstração, é definida uma função que mostra o valor relaxado, o valor arredondado e o gráfico, com os vértices em
mostrados em vermelho.
Encontre um corte máximo aproximado usando o procedimento mostrado anteriormente e compare com o resultado exato.
Encontre o corte máximo de um gráfico de grade.
Encontre o corte máximo para um gráfico aleatório.
Compare os tempos de cálculo para os algoritmos relaxados e exatos para um gráfico de Peterson.