Facebook Hacker Cup – Round 2 (Continuação…)

Março 27, 2011

A final do facebook hackercup aconteceu dia 11 de Março em Palo Alto. O campeão foi o Petr Mitrichev.

Eu, como mero mortal (:P), ainda estou tentando entender as soluções dos problemas do round 2. Nesse post vou comentar a solução do problema Scott’s New Trick.

A descrição do problema é bem simples: dados dois vetores A e B de inteiros aleatórios, com tamanhos N e M, respectivamente, um primo P e um inteiro 1 ≤ L ≤ P contar quantos índices 1 ≤ i ≤ N e 1 ≤ j ≤ M satisfazem (A[i] * B[j]) mod P < L.

Solução:

Bom, é trivial resolver esse problema em O(NM), enumerando todos os índices. O problema é que 2 ≤ N, M ≤ 10.000.000, então temos que pensar em uma solução melhor.

Uma segunda ideia é criar vetores de frequências fA e fB, ambos de tamanho P. A entrada fA[i] guarda quantos elementos v de A existem tal que v % P = i. O vetor fB é definido analogamente para B. Em O(P^2) percorremos todos os i e j. Se i * j % P < L, somamos fA[i]*fB[j] na conta final. Temos que P < 250.000, mas ainda é inviável rodar 20 testes em menos 5 minutos (que era o tempo para submeter as respostas).

Minha ideia durante a competição foi tentar paralelizar esse programa usando OpenMP em uma máquina com 4 cores. Consegui reduzir o tempo de execução para 1 minuto no pior caso. Porém, eu ia precisar de umas 5 ou mais máquinas dessas para conseguir submeter a tempo :( Ouvi dizer que alguém passou esse problema com esse algoritmo paralelizando em um cluster!

Parece que a maior parte das pessoas que passaram o problema, implementou o algoritmo de Karatsuba (o autor do algoritmo é russo e não japonês como o nome sugere, hehe). Vou estudar essa solução posteriormente, mas agora quero apresentar a solução bastante inteligente do meret, que melhora o desempenho do código usando teoria dos números e programação dinâmica.

Vamos continuar com os vetores fA e fB. Notamos que a soma que estamos buscando é dada por

(1)

O primeiro somatório conta os elementos onde os elementos de A são 0 (% P). Logo a multiplicação deles por quaisquer elementos de B vai ser sempre 0, e menor do que L, já que L ≥ 1.

Para entender o segundo somatório, considere um dado j. O valor inv(j) é o inverso modular de j, ou seja, é um número x tal que j * x ≡ 1 (mod P). Ele conta os números com produto igual a j*(k*inv(j)) % P, como multiplicação modular é comutativa e associativa, esse produto é simplesmente k. Por isso k vai até L-1.

Note que a restrição de P a primo é importante para que haja exatamente um único inverso modular para todo j de 0 a P-1. Além disso, todas as contas de índice são módulo P.

Agora, considere inteiros ‘c’ e ‘i’ tais que c ≡ i*j (mod P), equivalentemente, c * inv(j) ≡ i (mod P). Dados dois inteiros x e y, podemos escrever x como

(2)

Pois é o quociente e x % y é o resto da divisão. Sendo o índice k (da equação (1)) e c ambos inteiros, podemos escrevê-los na forma da equação (2). Além disso, multiplicando ela por inv(j) ficamos com

Fazendo módulo P e substituindo c * inv(j), temos

(3)

Na equação (1) podemos colocar para fora do somatório de k o termo fA[j]. Fixando um dado j, temos

Agora vamos substituir cada fB[k * inv(j)] pelo equivalente em (3). Para k = 0 até c-1, , então os índices serão

.

Para k = c até 2c-1,

e assim por diante, até que , onde os índices serão


Vamos reorganizar esse somatório agrupando os índices de forma que (k % c) sejam iguais, ou seja, soma os termos da primeira coluna, depois os termos da segunda coluna e por aí vai. O primeiro grupo fica,

(4)

O segundo grupo fica (5)

O k-ésimo grupo fica (6)


Note que são c grupos dessa forma. Introduzimos diversas variáveis, rearranjamos os termos, mas o somatório continua o mesmo. O intuito dessas complicações é permitir o cálculo rápido dos grupos acima. Para isso, dado um i, considere o vetor V, onde V[k] = i*k % P para k = 0, …, P-1.

A sacada da solução é notar que todo grupo de índices definido acima, corresponde a um intervalo de V. É fácil ver que o primeiro grupo de índices (eq. (4)), corresponde ao intervalo 0 a de V.

O segundo grupo é mais difícil de enxergar. Será que existe um intervalo de V correspondente a (5)? O primeiro termo é inv(j). Queremos encontrar um k’ tal que k’i ≡ inv(j) (mod P). Para tal, multiplique essa igualdade por j, ficando com k’*i*j ≡ 1 (mod P). Substituindo i*j por c, temos que k’c ≡ 1 (mod P) ou seja, k’ é o inverso modular de c!

Agora os índices do segundo grupo aumentam de i em i, então é fácil ver que eles formam um intervalo em V (possivelmente dando a “volta” no vetor). Como são termos, dá pra descobrir o intervalo de V, que será de inv(c) a inv(c) + .

Para um k genérico, é possível mostrar que k’ = k * inv(c). O intervalo fica de k*inv(c) a k*inv(c) + .

Vamos pré-computar um vetor com a soma acumulada dos elementos de fB indexados por V, denotado S, ou seja

Para todo n de 0 a P-1. Esse vetor pode ser calculado em O(P). Para cada grupo de índices, correspondente ao intervalo (lb, ub) em V, calculamos a soma

Dado um j, a complexidade fica O(P) para construir S e O(c) para computar as somas dos grupos de índices.

A primeira abordagem é, para cada j, escolher um i que minimize c. Claramente o i que estamos procurando é inv(j), pois nesse caso c=1. Aí podemos calcular as somas dos grupos em O(1), mas a complexidade de calcular S é O(P). Isso torna o algoritmo O(P^2), o que é tão ruim quanto o algoritmo mais simples.

No outro extremo, como S só depende de i, podemos escolher um i fixo para todo j e calcular c em função de i e j. Aí calculamos S apenas uma vez em O(P) e aí para cada j calculamos a soma em O(c). A complexidade fica O(P + P*C), onde C é o maior valor de c considerando todos os j’s. O problema é que C pode ser da ordem de P.

A ideia é usar uma abordagem híbrida. Escolhemos um i que minimize c, mas limitamos o valor de i a √P. Calculamos então o vetor imin, onde para cada j, imin[j] contém i (1 a √P) que minimize c. Aí então calculamos S apenas √P vezes. A complexidade fica O(P√P + P*C). Porém C ainda pode ser da ordem de P. Podemos apertar a análise da complexidade como O(P√P + ∑(c)), onde ∑(c) é a soma dos c’s para cada j.

Aí entra uma conjectura/teorema de que ∑(c) é O(P√P). (No final das contas isso estraga a beleza da solução. Seria legal ver a prova disso…). Com tudo isso, temos a complexidade O(P√P), que é suficiente para passar no tempo.

Conclusão

Apesar da conjectura, a solução do meret tem várias ideias interessantes. Vale a pena ver a implementação dele (dá pra baixar no site do Facebook). Não fiquei muito empolgado para implementar essa solução, mas quero ainda estudar as soluções usando o algoritmo de Karatsuba. Fica para um próximo post.

Anúncios

Programming Pearls: Parte 3

Março 21, 2011

Eu ia descrever as colunas 11 a 15 nesse post, mas devido à grande quantidade de informação e coisas interessantes para descrever o post ficaria gigantesco. Vou me restringir às colunas 11 a 13. Em um post futuro fecho com as colunas 14 e 15.

Coluna 11: Sorting

Aqui são revisados os algoritmos de insertion sort e quicksort. O que achei mais interessante nessa coluna foi um exercício em que se pede para ordenar um conjunto de strings de bits de diferentes tamanhos. A solução apresentada é bem elegante:

std::string *x[N];
void bsort(int lo, int up, int depth){
    if(lo <= up) return;
    for(int i=lo; i<=up; i++)
        if(x[i]->length() == depth)
            std::swap(x[i], x[lo++]);
    int m = lo;
    for(int i=lo; i<=up; i++)
        if(x[i]->at(depth) == '0')
            std::swap(x[i], x[m++]);
    bsort(lo, m-1, depth);
    bsort(m, up, depth + 1);
}

No código C++ acima, o conjunto de strings é armazenado em um array de ponteiros para std::string. O uso de ponteiros é necessário para que a troca de elementos seja feita em O(1) e não no tamanho das strings.

A hipótese em cada chamada da recursão é de que o intervalo [lo, up] possui os depth-1 primeiros bits iguais.
O primeiro for trata se separar as strings que têm tamanho exatamente depth, já que elas virão primeiro na ordenação lexicográfica.

O segundo for, separa as strings restantes pelo próximo bit em que elas diferem, ou seja, o depth-ésimo bit. Essa separação é semelhante àquela feita no pivoteamento do quicksort. Depois desse laço, as strings entre [lo, m-1] têm os depth primeiros bits iguais e aquelas entre [m, up] também. Logo, podemos chamar recursivamente a função pois mantivemos a invariante.

É possível verificar que estamos percorrendo cada string um número de vezes igual a seu comprimento. Em cada chamada estamos avançando um bit e depois que atingimos seu comprimento, deixamos a string de lado.

Coluna 12: A Sample Problem

Nessa coluna é abordado o problema de se gerar m números aleatórios entre 1 e n, sem repetição. São apresentados vários algoritmos muito elegantes! A primeiro deles foi proposto pelo Knuth. Segue uma implementação em C++

void gen_knuth(int m, int n){
    for(int i=0; i<n; i++)
        if(rand() % (n-i) < m){
            std::cout << i << "\n";
            m--;
        }
}

Onde a função rand() retorna um inteiro entre 0 e RAND_MAX (que depende de implementação, mas é pelo menos 32767). O que se deseja com rand() % (n-i) é gerar inteiros entre 0 e n-i-1, inclusive, com probabilidade uniforme. A distribuição não fica totalmente uniforme se RAND_MAX não for múltiplo de n-i, mas na prática é uma boa aproximação.

O algoritmo acima imprime m valores com probabilidade uniforme. A prova da uniformidade das probabilidades está no livro do Knuth, mas ainda não tive como consultá-la. Por outro lado, é fácil mostrar que o algoritmo sempre imprime m elementos. Ele não imprime mais do que m elementos pois quando m = 0, o if é sempre falso. Se n-i <= m, o if é sempre verdadeiro. Esse algoritmo é O(n) de tempo e O(1) de espaço. Se n for muito grande, o algoritmo fica muito lento.

Uma outra versão é usando conjuntos para marcar quais elementos já foram selecionados. Um código se encontra abaixo, usando a implementação set da STL. Para quem não sabe, essa estrutura é implementada usando árvore binária balanceada (acho que é a red-black tree), ou seja, inserir um elemento em um set, decidir se um elemento está no set ou remover um elemento de um set são operações que levam tempo O(log n).

void gen_set(int m, int n){
    std::set<int> s;
    while (s.size() < m)
        s.insert(rand() % n);
    std::set<int>::iterator it;
    for(it = s.begin(); it != s.end(); it++)
        std::cout << *it << "\n";
}

Nessa versão sorteamos um número até tirar um que não tenha sido escolhido ainda. Note que esse algoritmo é probabilístico. Assim, podemos descrever sua complexidade em termos do número esperado de vezes que teremos que sortear um número até encontrar m elementos distintos. Esse problema é conhecido como o problema do colecionador de figurinhas e diz que o número esperado de sorteios necessários é O(n log n). Como a inserção é feita em O(log n), o algoritmo tem complexidade O(n log^2 n).

Robert Floyd propôs uma solução que não faz inserções desnecessárias e é determístico.

void gen_floyd(int m, int n){
    set<int> s;
    for(int j = n - m; j < n; j++){
        int t = (rand() % (j+1));
        if(s.find(t) == s.end()) s.insert(t);
        else s.insert(j);
    }
    set<int>::iterator it;
    for(it=s.begin(); it!=s.end(); it++)
        cout << *it << "\n";
}

Esse algoritmo é O(m log n). Não encontrei a prova de que nesse algoritmo os elementos são escolhidos de maneira equiprovável.

Um dos exercícios dessa coluna pede para escolher um número aleatório com probabilidade uniforme de uma lista, sem que se conheça o tamanho da lista! Pode-se pensar que é a versão online do algoritmo de escolher um número aleatório de uma lista.

O algoritmo é bem simples:

int rand_online(){
    int v, pick, cnt = 1;
    while (std::cin >> v){
        if (rand() % cnt == 0)
            pick = v;
        cnt++;
    }
    return pick;
}

O algoritmo lê os elementos a serem sorteados sem no entanto armazená-los. A cada elemento lido v, o algoritmo troca o elemento anteriormente armazenado por v com probabilidade 1/i. Dá para mostrar que a chance de um elemento ser escolhido é uniforme.

Coluna 13: Searching

Fiquei com a sensação de que o nome dessa coluna não espelha muito bem seu conteúdo. Aqui basicamente são apresentadas diferentes estruturas de dados como: array e listas ligadas para manter os elementos do conjunto de maneira ordenada, uma árvore de busca binária (não balanceada, mas que funciona bem nesse caso porque os números inseridos são aleatórios), além de estruturas especializadas que aproveitam o fato dos elementos do conjunto serem inteiros como um array de bits onde o i-ésimo bit é 1 se o inteiro i está no conjunto e uma espécie de hash, que vale a pena detalhar um pouco.

Dado que queremos sortear m elementos de 1 a n, criamos um array de m ponteiros para listas ligadas. Cada lista ligada representa um bucket. O primeiro bucket armazenará os valores de 0 a n/m-1, o segundo de n/m a 2(n/m)-1 e assim por diante. Ao inserir um número t no conjunto, mapeamos esse valor para o bucket correto através de k = t/(n/m). Aí basta inserir na lista ligada apontada pelo bucket k. Embora a inserção na lista seja linear no seu tamanho, como vamos inserir apenas m elementos com valores distribuídos de maneira uniforme, as listas em cada bucket tem tamanho esperado 1! Então essa inserção é muito rápida na prática.


Facebook Hacker Cup – Round 2

Março 11, 2011

Recentemente teve uma competição promovida pelo Facebook, chamada Facebook Hacker Cup. Por mais que o nome sugira outra coisa, essa competição é nos moldes da Maratona de Programação e muito similar ao Google Code Jam.

Teve uma fase de qualificação, onde bastava fazer pelo menos um problema. Depois teve o Round 1 que era dividido em três partes: A, B e C. Você podia tentar qualificar para o Round 2 em qualquer uma delas desde que não tivesse conseguido em uma anterior.

Essas duas primeiras fases foram relativamente tranquilas, mas o Round 2 foi muito difícil! Os 300 primeiros dos ~3000 classificados iriam ganhar uma camiseta, mas só 150 pessoas fizeram pelo menos um problema e eu não estava entre elas :/

Os 25 primeiros colocados vão competir na final onsite lá em Palo Alto. Até onde eu sei não há brasileiros.

Vou apresentar apenas o problema mais fácil dessa etapa. Os outros eu ainda não sei como fazer :P Se eu descobrir faço um novo post.

Bonus Assignments

O descrição do problema se encontra aqui. No problema você deve distribuir uma certa quantidade de dinheiro para N trabalhadores para eles comprarem refrigerante, com a restrição de que o trabalhador que ganhar menos não deve ganhar menos do que A ou mais do que B. O trabalhador que ganhar mais não deve ganhar menos do que C ou mais do que D. Uma restrição adicional é que pelo menos um trabalhador não vai conseguir torrar todo o seu dinheiro em refrigerante. Você não sabe o preço exato do refri, só que é mais do que $1. Queremos saber quantos jeitos temos de distribuir dinheiro, satisfazendo essas restrições. A resposta deve ser módulo 1,000,000,007.

A primeira observação é que, para que sempre sobre algum trabalhador que não consiga torrar todo o seu dinheiro com refri, independente do custo desse, deve existir pelo menos dois trabalhadores que recebam montantes x e y primos entre si. Caso contrário, se todo par tivesse montante com algum divisor comum mdc > 1, então para um refri com esse valor todos conseguiriam torrar seu dinheiro.

O problema se reduziu a contar quantas combinações existem para N elementos, de modo que o valor do menor elemento esteja entre [A, B] e do maior entre [C, D] e exista pelo menos um par de elementos com valores primos entre si.

Solução:

Vamos por partes. Primeiro, como contar quantas combinações existem de N elementos, sendo que o valor deles deve estar entre [A, D]? Por exemplo, N = 3, A = 1, D = 5. Cada elemento pode assumir o valor {1, 2, 3, 4, 5}. Como eles são independentes, há 5^3 combinações. De maneira mais geral, temos (D-A+1)^N.

Porém, queremos que o menor elemento tenha valor de no máximo B. Por exemplo se B = 2, na conta acima estamos contando o vetor [3, 3, 5], cujo menor elemento é 3. Então queremos jogar fora os vetores cujo menor elemento sejam maior do que B. Esse número é justamente quantas combinações de N elementos temos com valor entre [B+1, D]. Ou seja, devemos descontar (D – B)^N.

De igual maneira, ainda estamos contando vetores cujo maior elemento seja menor do que C. Por exemplo, se C=4, temos [1, 1, 1] na conta acima. Vamos jogar fora aqueles vetores cujo maior elemento seja menor do que C, ou seja, aqueles com N elementos de valores entre [A, C-1], dado por (C – A)^N.

Ficamos com um problema. Observe que o vetor [3, 3, 3] é um vetor com valores entre [A=1, C-1=3] e [B+1=3, D=5]. Ou seja, removemos ele duas vezes! De modo geral, removemos todos os vetores que têm valores entre [B+1, C-1] duas vezes. Devemos repô-lo com (C – B – 1)^N. Observe que essa interseção só ocorre se C > B+1.

Bom, sem a restrição de ter pelo menos dois valores primos relativos a conta é basicamente:

(D-A+1)^N – (D – B)^N – (C – A)^N + (C – B – 1)^N,

onde o último termo é zero se C <= B+1.

Nessa contagem estamos contando tanto os vetores com pelo menos dois primos relativos, quanto aqueles em que nenhum par é primo relativo, ou seja, os vetores para os quais todos os valores tem um divisor comum maior do que 1. Vamos tentar encontrar aqueles com mdc=2. Por exemplo, para N = 3, A = 3, B = 4, C = 4, D = 7. Um exemplo é [4, 6, 4]. Claramente podemos dividir esse vetor por 2, resultando em [2, 4, 2]. Fica claro que podemos dividir todos os limites por 2 e obter um subproblema que é justamente a quantidade de combinações onde todos os valores são pares.

Assim, dividimos A, B, C e D por 2 para obter A’=2, B’=2, C’=2, D’=3. Note que usamos teto para os limites inferiores A e C, mas chão para os superiores B e D, pois não queremos considerar um intervalo maior do que o original. Note também que ao dividir por 2 e contar, estamos considerando os casos com mdc=4, mdc=8, etc. Ou seja, só precisamos remover as divisões por primos!

Bom, basta então dividir por todos os primos para os quais os intervalos resultantes tenham algum vetor válido. Um limite suficiente é tentar dividir por todos os primos menores ou iguais que D. Porém, temos novamente um problema de remoção repetida. Ao contar os que têm 2 como mdc e os que têm 3 como mdc, estamos contando duas vezes aqueles que têm 6 como mdc! Por isso precisamos usar o princípio da inclusão-exclusão. Dá para fazer isso recursivamente.

Acho que essa teoria é suficiente para resolver o problema. Tem o detalhe de achar primos de forma eficiente, que pode ser feita com o crivo de Eratóstenes e fazer a exponenciação modular de forma rápida.

Tem uma pegadinha adicional, que eu só descobri depois que implementei: nada impede que B > D ou C < A. Algumas das contas podem dar errado por causa disso, mas note que o resultado não muda se fizermos B = min(B, D) e C = max(C, A) nesse caso.

Minha implementação em C++ está aqui. Baseei minha análise e código na solução do kalinov.


Formulações do TSP

Março 4, 2011

O problema do caixeiro viajante (do inglês Traveling Salesman Problem, abreviado como TSP) é o problema mais conhecido e estudado em otimização combinatória. Creio que alguns dos motivos para isso seja sua definição simples, sua dificuldade e sua aplicabilidade prática.

A definição é de fato simples. Imagine que você tem n cidades e entre cada par de cidades existe uma rodovia com uma dada distância. Você deseja partir de uma das cidades, percorrer as outras exatamente uma vez e então retornar para a cidade de origem de forma a minimizar a distância percorrida. Em termos de teoria de grafos, dado um grafo completo de n vértices e custo nas arestas, encontrar um ciclo com exatamente n vértices de menor custo.

O TSP é conhecidamente NP-difícil. Porém, entre os problemas NP-difíceis, há ainda uma diferença na dificuldade entre eles. Algoritmos de aproximação podem dar uma noção dessa diferença. Alguns problemas admitem algoritmos com fatores de aproximação arbitrariamente próximos de 1, enquanto outros não admitem sequer fator de aproximação constante.

O problema da mochila por exemplo, é um dos problemas NP-difíceis mais “tratáveis”. Ele pertence à classe dos PTAS (Polynomial Time Approximation Scheme), o que significa que ele pode ser aproximado por um fator tão próximo de 1 quanto se queira, embora o tempo de execução aumente em função dessa proximidade. Por outro lado, a versão geral do TSP não pode ser aproximada por um fator constante a menos que P = NP. Por isso, o algoritmo do TSP é um dos problemas mais difíceis da computação, embora afirma-se que abelhas saibam resolvê-lo.

Formulações

Há pelo menos três formulações de programação linear inteira para esse problema. Uma delas foi publicada em 1960, por Miller, Tucker e Zemlin e que denominaremos MTZ, é baseada em fluxos em redes. Considere um grafo direcionado completo D(V, A) de n nós e custo nas arestas. Seja uma variável binária que vale 1 se a aresta (i,j) está na solução, e 0 caso contrário. Denotando o custo de uma aresta (i,j) por , a função objetivo é simplesmente

Como queremos encontrar um ciclo que passe por todos os vértices, cada vértice deve ter exatamente uma aresta entrando e outra saindo, o que é gatantido com as seguintes restrições

(1) Para todo

(2) Para todo

Somente com essas restrições, as soluções serão coberturas de vértices por ciclos, ou seja, teremos um ou mais ciclos de forma que cada vértice estará contido em exatamente um ciclo. A ideia dos autores de [1] é introduzir variáveis representando potenciais de um vértice v. Sempre que uma aresta (i,j) é usada, o potencial do vértice j tem que ser maior do que i. Isso criará um impedimento na criação de ciclos, da mesma maneira do modelo para o caminho mais longo, conforme esse post anterior.

Porém, isso também impedirá a formação do ciclo que estamos procurando. O truque é não usar essa restrição sobre um dos vértices, por exemplo o vértice 1. Dessa forma as desigualdades impedirão quaisquer soluções que contenham subciclos que não incluam o vértice 1. As únicas soluções que satisfarão isso, além de (1) e (2), são os ciclos de tamanho n. A desigualdade fica,

(3) Para todo

Onde M é uma constante suficientemente grande. Se , a desigualdade fica redundante. Se , forçamos .

A segunda que vamos apresentar é devido a Dantzig, Fulkerson e Johnson, ou DFJ. O modelo possui as variáveis e as restrições (1) e (2). A diferença fica por conta da eliminação de subciclos.

(4) Para todo

É possível mostrar que se, para um subconjunto não-próprio S de V, existem |S| ou mais arestas, então existe pelo menos um ciclo. O problema é que o número de desigualdades (4) é exponencial e para isso um algoritmo de planos de corte, como o Branch and Cut, deve ser usado. Uma maneira de reduzir o número dessas desigualdades é observar que se uma solução satisfaz (1) e (2) e existe um subciclo de tamanho maior do que |S|/2, então existe um subciclo de tamanho menor do que |S|/2, de forma que podemos considerar as desigualdades (4) apenas para

Uma outra maneira de se eliminar subciclos é através das desigualdade chamadas cut set constraints, dadas por

(5) Para todo

A ideia aqui é que dada uma cobertura por ciclos contendo subciclos, existe uma maneira de separar o conjunto de vértices em 2, de forma que cada subciclo fique exatamente de um dos lados, ou seja, nenhum aresta “cruza” essa partição. Note que o número de desigualdades (5) também é exponencial.

Conclusão

Embora o modelo MTZ tenha sido desenvolvido depois do DFJ, e tenha um número polinomial de desigualdades, na prática o DFJ é bem mais eficiente. A explicação pode ser dada pela combinatória poliédrica, já que é possível mostrar que o modelo DFJ está contido no MTZ. Em um post futuro, pretendo apresentar um esboço dessa prova.

Uma questão que surgiu ao estudar as formulações é a relação entre os modelos com a desigualdade (4) e (5). Serão eles equivalentes? Um está contido no outro? Essa é outra pergunta que pretendo pesquisar.

Referências

[1] Miller, Tucker and Zemlin — Integer Programming Formulation of Traveling Salesman Problems
[2] Dantzig, Fulkerson and Johnson — Solution of a Large-Scale Traveling-Salesman Problem