Como instalar concorde - C/C++ TSP Solver

O Traveling Salesman Problem (TSP) também conhecido com o Problema do Caixeiro Viajante é um problema clássico de otimização que consiste em determinar a menor rota possível para percorrer uma série de localidades e retornar ao mesmo ponto.

Ele é um problema NP-Difícil e possuí diversas abordagens heurísticas na literatura para solucionamento, tais como Algoritmos Genéticos, Redes Neurais, Simulated Annealing, entre outros. As heurísticas não garantem encontrar a solução ótima do problema, mas na maioria das vezes são capazes de encontrar boas soluções, muito próximas da otimalidade em um tempo computacional viável. Sendo assim, uma abordagem de resolução exata para um problema de grande dimensão pode ser totalmente inviável devido a alta complexidade computacional.

Para pequenos problemas é possível aplicar métodos exatos, obtendo assim a rota com o menor custo possível. O TSP geralmente é abordado como um sub-problema de uma configuração de rede ou rota mais complexa, como um problema de roteamento de veículos, onde é possível sub-dividir as rotas em circuitos menores sob um limite de pontos pré estabelecido. Viabilizando assim uma abordagem exata para o problema. A Figura 1 mostra um exemplo de problema de roteamento com limite de 6 nós por ciclo.

Concorde

Boa parde das pesquisas desenvolvidas, utilizam linguagens de baixo nível como C e C++ para aplicação e resolução de tais problemas. Desta forma podemos utilizar o Concorde, que é um algoritmo desenvolvido em ANSI C para solucionamento do problema TSP. O Concorde foi desenvolvido por William Cook e é de livre utilização para fins de pesquisa acadêmica. Mais detalhes sobre o mesmo podem ser encontrados em sua página oficial.

O Concorde pode ser utilizado em conjunto com o CPLEX, porém também existe a possibilidade de configurá-lo para aplicação o QSOPT que é um solver gratuito e de fácil utilização.

Mesmo sendo desenvolvido em C, com simples modificações é possível utilizar o mesmo também em C++. Neste artigo iremos abordar a sua instalação e configuração para ambiente Linux. Sendo que a distribuição utilizada é um Ubuntu de 64 bits, mas o presente método também foi testado em outras distribuições baseadas no Debian, como por exemplo o Linux Mint.

Download

Para utilizar o Concorde no Linux é necessário baixar o seu código fonte e compilá-lo em sua máquina, para isso é necessário fazer o download dos seguintes itens:

Concorde - Código Fonte do Algoritmo.

QSOPT - Solver gratuito para compilação.

A última versão disponibilizada do Concorde foi publicada em 19 de Dezembro de 2003 e não teve atualizações desde então, já o QSOPT possui uma versão estável para sistemas 32bits, mas caso você possua um sistema de 64bits é possível utilizar a versão beta disponibilizada pelo mesmo.

Para compilar o código fonte é necessário ter instalado em seu computador o pacote build-essential, que pode ser obtido através do comando:

sudo apt-get install build-essential

Na minha instalação, eu optei por instalar os arquivos do QSOPT na pasta /opt/qsopt64, mas você pode colocar a biblioteca em qualquer outra pasta do sistema. Mas caso mude, não se esqueça de substituir o caminho nos próximos passos também.

Criando a pasta no diretório /opt

sudo mkdir /opt/qsopt64

Movendo os arquivos

sudo mv ~/Downloads/qsopt /opt/qsopt64/qsopt
sudo mv ~/Downloads/qsopt.a /opt/qsopt64/qsopt.a
sudo mv ~/Downloads/qsopt.h /opt/qsopt64/qsopt.h

Se seus arquivos do concorde estiverem na pasta de Download do linux, basta descompacta-los e utilizar o seguinte comando para move-los.

sudo mv ~/Downloads/concorde /opt/concorde

Após isso, basta configurar o concorde para utilizar o qsopt e compilar. A configuração é simples, basta acessar a pasta do concorde via terminal e executar o arquivo de configuração utilizando parâmetro -with-qsopt, assim como mostrado abaixo:

cd /opt/concorde
sudo ./configure -with-qsopt=/opt/qsopt64

Para compilar, basta executar o make pelo terminal, dentro da pasta do concorde:

make

Se você pretende utilizar o Concorde através do C++, será necessário um simples modificação em seu cabeçalho. A modificação é necessária pois o concorde é escrito em C, e algumas palavras reservadas do C++ são utilizados para nomear ponteiros da biblioteca. Para isso basta substituir as palavras *new por *novo e *class por *classe. Isso não afeta a biblioteca pois são termos utilizados apenas em protótipos de funções da biblioteca.

Para isso basta utilizar um simples editor de texto, e substituir os termos mencionados anteriormente. No caso do Ubuntu você pode utilizar o gedit:

sudo gedit /opt/concorde/concorde.h

A substituição pode ser feita através do comando CTRL+H ou através do menu Pesquisar > Substituir

Opcional

Não é obrigatório, mas pode auxiliar no processo de compilação de sua aplicação. O C++ reconhece uma biblioteca em determinado diretório através do prefixo lib, desta forma é necessário criar links simbólicos para facilitar a importação das mesmas através do Makefile. Para criar os links simbólicos basta executar os seguintes comandos:

sudo ln -s /opt/concorde/concorde.a /opt/concorde/libconcorde.a

Você pode fazer o mesmo para o QSOPT

sudo ln -s /opt/qsopt64/qsopt.a /opt/qsopt64/libqsopt.a

Pronto! O Concorde está pronto para ser utilizado. Para testar, faça o download desse projeto de teste, configure os caminhos das bibliotecas no Makefile caso tenha alterado o caminho padrão e execute o comando

make && make run