George Dantzig e o Algoritmo Simplex

George Dantzig (1914-2005) pode ser considerado o pai da programação linear, pois ele é o inventor do Simplex, o primeiro algoritmo para resolução de programas lineares. No pior caso, o simplex tem complexidade exponencial em função do tamanho da entrada e já foram desenvolvidos algoritmos polinomiais que resolvem programas lineares como o método dos pontos interiores. Na prática porém, o algoritmo simplex se comporta muito bem. Além disso possui características que os fazem ideais para os algoritmos de Branch and Bound, que resolvem programas lineares inteiros.

Diz a lenda que uma vez Dantizig chegou atrasado para o primeiro dia de aula de estatística na Universidade de Berkeley. Quando entrou, viu dois problemas escritos na lousa e, pensando serem tarefas para casa, anotou-os em seu caderno. Após alguns dias, entregou os exercícios ao professor e se desculpou por demorar tanto para resolvê-los, por estarem mais difíceis do que o normal. O professor pareceu não dar muita importância na hora, mas depois um tempo foi revelar a Dantizig que ele tinha resolvido dois problemas abertos em estatística.

O filme Gênio Indomável inspirou-se nessa história. Para quem não viu ou não lembra, Will Hunting era um faxineiro de uma Universidade, encrenqueiro, com passagens pela polícia e um gênio da matemática. Certa vez professores discutiam sobre um teorema em uma lousa e após irem embora, deixam o enunciado do teorema escrito. No dia seguinte o teorema está resolvido por um autor anônimo. Mais tarde descobrem se tratar do faxineiro e o filme se desenrola com os professores tentando convencer Hunting a estudar matemática e procurar um psicólogo para refrear seus ímpetos. É um filme que eu gostei muito e recomendo.

Uma paródia do filme, Perry Bible Fellowship

Em 1975, os economistas Tjalling Koopmans e Leonid Kantorovich foram laureados com o prêmio Nobel por sua teoria de alocação ótima de recursos, que era essencialmente programação linear. Injustamente Dantizig não foi premiado. Para quem tem interesse em saber mais sobre ele, eis uma biografia mais completa.

Enfim, o principal objetivo do meu post foi falar sobre um outro post que eu li no blog de teoria Gödel’s Lost Letter and P=NP, que começa falando sobre Dantzig para então apresentar uma excelente introdução a PLI. No post ele também apresenta uma modelagem para o problema de decidir se um grafo cúbico tem uma 3-coloração, que é NP-Completo.

Ele utiliza uma técnica interessante para modelar uma variável que pode assumir valores discretos não-contíguos, no caso 1, 2 e 4. Sejam variáveis binárias e que representa a cor de um vértice . Temos o modelo para cada :

(1)
(2)

Para cada três vértices adjacentes :

(3)

A desigualdade (2) diz que exatamente um, entre deve valer 1. Combinada com (1), temos que vale 1, 2 ou 4. A única forma para (3) ser satisfeita é com 1 + 2 + 4, ou seja devem ter cores diferentes, justamente a restrição do problema da 3-coloração. Assim, se existir uma solução satisfazendo tais desigualdades, o grafo possui uma 3-coloração.

Exemplo de uma 6-coloração de um Grafo

Há um problema mais genérico do que a 3-coloração em grafos cúbicos, que é determinar se um grafo G qualquer possui uma k-coloração. Definimos variáveis binárias se o vértice v possui cor c e 0 caso contrário. Temos o seguinte modelo:

(4) Para todo vértice v = 1,…,n,

(5) Para todo par de vértices adjacentes i e j, e toda cor c,

A igualdade (4) força que todo vértice tenha uma única cor. A igualdade (5) impede que dois vértices adjacentes tenham a mesma cor. Se existir algum y que satisfaz todas as igualdades, o grafo possui uma k-coloração.