Metodologia para acelerar a busca por soluções de problemas
similares ao Caixeiro Viajante
Maria José Pinto Lamosa
Instituto de Estudos Avançados (IEAv) - Divisão de Geointeligência (EGI)
São José dos Campos, SP
E-mail: [email protected]
Fernando Nascimento Coelho
Nei Yoshiriro Soma
Instituto Tecnológico de Aeronáutica (ITA) - Departamento de Engenharia de Computação
São José dos Campos
E-mails: [email protected] , [email protected]
Resumo: Este trabalho apresenta uma metodologia que visa acelerar o tempo de busca por
soluções para problemas similares ao Problema do Caixeiro Viajante, utilizando agregação de
equações Diofantinas. Além disso, propõe realizar um pré-processamento que, utilizando o
limitante de Frobenius, busca reduzir ainda mais o tempo de resolução do problema.
Introdução
Problemas que envolvem otimização de rotas em uma determinada região são conhecidos
como problemas de roteamento e têm despertado o interesse de pesquisadores devido à
dificuldade e complexidade de resolução. Além disso, estes problemas possuem aplicação
direta na prática e podem trazer economia de recursos aos setores interessados, quando rotas
mais elaboradas são geradas. Dentre os problemas de roteamento mais estudados na literatura,
podemos citar o problema do caixeiro viajante (TSP, do inglês Traveling Salesman Problem).
O objetivo deste trabalho consiste em propor uma metodologia para tratar problemas
similares ao TSP, ou seja, que podem ser modelados através de equações matemáticas cujas
variáveis devem assumir somente valores inteiros não-negativos. Esses sistemas, em geral, são
resolvidos de forma ineficiente, no sentido de que é demandado um tempo muito alto, muitas
vezes impraticável para encontrar um conjunto de soluções possíveis. Diante desse impasse
surgiu a ideia de agregar as equações desses sistemas em uma única equação que possuísse um
conjunto solução que contivesse o mesmo conjunto solução que o sistema original. Com essa
única equação advinda do processo de agregação poder-se-ia descobrir de modo rápido
(polinomial) a existência ou não de solução para muitos casos através do limitante de Frobenius
[7]. Assim, para muitos problemas, seria possível verificar rapidamente a existência ou não de
uma solução, que é muito interessante do ponto de vista prático.
Problema do Caixeiro Viajante
Neste problema, um caixeiro viajante, começando de uma cidade origem, visita
exatamente uma vez cada cidade de uma lista pré-definida e retorna para a origem, buscando
minimizar a distância percorrida [3].
Formulação matemática
Considerando que o problema pode ser modelado como um problema em grafo, seja: n, o
número de cidades a serem visitadas (número de vértices do grafo), (i, j) as arestas do grafo e dij
o custo (distância) para percorrer a aresta (i, j). Ainda, considere a variável xij indicando o fluxo
da rota, ou seja, será igual a 1 se a rota passar pela aresta (i, j) e 0, caso contrário.
A formulação matemática do TSP proposta em [5] é dada por:
n
Minimizar
n
∑∑ d
(1)
ij x ij
i −1 j =1
799
n
Sujeito a:
∑x
ij
=1
∀j ∈ N
(2)
∀i ∈ N
(3)
∀S ⊂ N
(4)
∀(i , j ) ∈ N
(5)
i =1
n
∑x
ij
=1
j =1
∑x
ij
≤ S −1
i , j∈S
x ij ∈ {0 ,1}
A função objetivo (1) busca minimizar o custo total da viagem. As restrições (2) e (3)
exigem que o caixeiro chegue e deixe cada nó exatamente uma vez, respectivamente. As
restrições (4) evitam a formação de ciclos e as restrições (5) indicam que a variável de decisão
é binária, ou seja, indica se a aresta está ou não na rota definida.
Agregação de equações diofantinas
Uma equação diofantina é uma equação algébrica com coeficientes e variáveis inteiras.
Assim, um sistema de equações diofantinas é formado por um conjunto de equações com
coeficientes e variáveis inteiras. Transformar um sistema de equações lineares em uma única
restrição cujo conjunto solução de inteiros não negativos contém o conjunto de solução do
sistema original é interessante do ponto de vista de resolução de problemas de programação
linear inteira. Existem métodos descritos na literatura sobre agregação de equações para duas
ou mais equações.
O trabalho de Mathews [apud 4] permite agregar equações diofantinas com coeficientes
inteiros não-negativos, gerando uma única equação. A partir do trabalho de Mathews [apud 4],
outros resultados de agregações surgiram na literatura, como os propostos nos trabalhos de
Elimam e Elmaghraby [4] e Babayeve e Mardanov [2], que buscam diminuir os coeficientes da
equação agregada tornando, em geral, sua resolução mais rápida computacionalmente. Para um
melhor entendimento destes métodos e, para facilitar a obtenção da equação agregada para um
conjunto de equações lineares inteiras, implementamos um programa em linguagem C. Assim,
dado um conjunto de equações como entrada o programa fornece a equação agregada final.
Problema de Frobenius para equações Diofantinas
Considerando o sistema ax + by = c e d = mdc(a ,b ) , temos que toda combinação linear
de a e b é múltipla de d e, portanto, uma condição necessária para existência da solução é que
d c . Isso já pode ser utilizado como um pré-processamento, evitando buscas desnecessárias
por soluções. Na verdade, essa condição é necessária e suficiente, pois dada uma solução inicial
(x0 , y0 ) , ∀k ∈ Z o par ordenado  x0 + bk , y0 − ak  é também solução. Tal solução inicial
d
d 

sempre existe pois, pelo Teorema de Bézout [8], o máximo divisor comum de dois números
inteiros é uma combinação linear deles:
c
c
c
d = ax0′ + bxy 0′ ⇒ d = a x0′ + b xy0′
d
d
d
c
c
Tomando x0 = x0′ e y0 = xy0′ é uma solução desde que d c .
d
d
Considerando o caso em que os coeficientes de uma equação diofantina são todos
inteiros positivos e as variáveis não-negativas, o fato do máximo divisor comum dividir o termo
independente não garante a existência de uma solução. Com isto, surge o questionamento de
quais são os valores do termo independente que podem ser escritos como combinação linear
não-negativa dos coeficientes positivos da equação. Esse problema é conhecido como o
problema de Frobenius para equações Diofantinas, que propõe encontrar, dada uma equação
Diofantina linear inteira não-negativa, o maior inteiro que não pode ser escrito como
combinação linear inteira não-negativa dos coeficientes da equação. Dessa forma, pode-se
800
afirmar que, a partir de um certo valor, sempre há solução para a equação diofantina nos
inteiros não-negativos.
Para o caso onde a equação possui somente dois coeficientes inteiros não negativos
primos entre si (a1 e a2), o maior número que não pode ser escrito como combinação linear
inteira não-negativa destes coeficientes, vale [6]:
g (a1 a 2 ) = a1 a 2 − a1 − a 2
O desafio de encontrar o maior valor que não pode ser combinação linear inteira positiva
para valores maiores que dois é bem mais complicado e, com isto, não existe uma fórmula
fechada para casos maiores que dois [6]. Diversos trabalhos, porém, tratam de encontrar
fórmulas do limitante de Frobenius para três e quatro variáveis com certas restrições que
possibilitem uma fórmula explícita para o limitante. A seguir serão apresentados alguns
teoremas desses trabalhos.
Teorema 1
Se a1 , a 2 , a 3 são relativamente primos e a1 (a 2 + a 3 ) , então:
  a a  
g (a1 , a 2 , a 3 ) = −a1 + maxai  1 5 −i  
  a 2 + a 3   i =2 ,3
Teorema 2
Seja
um inteiro não-negativo. Então:
 a   a + 1
a + 2
g (a , a + 1, a + 2 , a + 4 ) = (a + 1)  + 
 + 2 4  − 1
4  4 


 a + 1  a   a + 1  a + 2 
a + 3
g (a , a + 1, a + 2 , a + 5 ) = a 
 +  5  +  5  +  5  + 2 5  − 1
5

   
 



a
a
 a + 1
a + 2 a + 3 a + 4  a + 5
g (a , a + 1, a + 2 , a + 6 ) = a   + 2   + 2 
+ 5

+
+
+
 −1
6 
6 
 6 
 6   6   6   6 
Para o caso geral, o nível de dificuldade é ainda maior, sendo praticamente inviável encontrar o
valor exato do limitante mesmo para poucas variáveis [6]. Além disso, o problema é NPCompleto para o caso geral. Assim, passa a ser mais interessante a busca por cotas que
indiquem apenas que a partir do valor desta cota sempre haverá solução. Uma cota interessante
e simples de encontrar é tentar reduzir o problema ao caso de duas variáveis. Considere que:
a 1 x1 + a 2 x 2 + K + a n x n = L
(6)
Para verificar se esta equação tem ou não solução, primeiro deve-se averiguar se
mdc (a1 , a 2 ,K , a n ) L pois, caso contrário, não há solução. Depois pode-se supor, sem perda de
generalidade, que a1 ≤ a 2 ≤ K ≤ a n . No caso em que existem dois coeficientes primos entre si,
escolhe-se o menor par em que isso ocorre. Supondo que seja o par a1 e a 2 e como xi ,
i = 1,K , n pertence aos inteiros não-negativos, pode-se se escrever a equação (6) ignorando os
termos a 3 , a 4 ,K , a n , como se procurássemos soluções em que x 3 = x4 = K = x n = 0 ,
resultando na seguinte equação:
a 1 x1 + a 2 x 2 = L
que possui um limitante de Frobenius, como descrito anteriormente: a1 a 2 − a1 − a 2 . Dessa
forma, se L for maior que esse valor, pode-se afirmar que a equação tem solução. Além disso,
pode-se afirmar que o limitante de Frobenius dessa equação, L*, tem uma cota superior igual a:
L* ≤ a1 a 2 − a1 − a 2 .
Por outro lado, se L ≤ a1 a 2 − a1 − a 2 não se pode afirmar nada sobre essa equação em
termos de solução. Vale ressaltar que essa análise foi possível, considerando o caso especial em
801
que existem dois coeficientes primos entre si. Isso pode ocorrer mesmo em casos que
mdc(a1 , a 2 ,K , a n ) = 1 , ou seja, mesmo que a condição do máximo divisor comum dividir o
termo independente ocorra, não há sempre garantia da hipótese feita ser válida. Portanto, o
método para propor essa cota superior vale somente nesses casos especiais.
Metodologia
O modelo (1)-(5) para o TSP permite transformar o problema com várias equações
inteiras, que refletem as restrições que são impostas naturalmente pelo problema, utilizando
agregação. A ideia principal da resolução proposta para o problema é reduzir as restrições
impostas ou um conjunto destas restrições, através de agregações de equações Diofantinas,
reduzindo o tempo para a busca de soluções. Há ainda casos em que se pode considerar um préprocessamento, parando a busca por uma solução, pois um conjunto de restrições não apresenta
solução. Isso evita, em muitos casos, processamentos desnecessários.
A análise descrita anteriormente consiste em agrupar algumas restrições do problema em
uma única equação que contenha o conjunto solução do sistema original de restrições,
diminuindo o tempo de processamento das mesmas. E ainda, através do limitante de Frobenius,
poder afirmar categoricamente em vários casos se há ou não solução para o sistema de forma
rápida.
Resultados
Alguns testes foram realizados para agregar equações Diofantinas que representassem
as restrições do TSP. Primeiramente, realizamos testes considerando as restrições (3). Para um
grafo com 4 vértices, a seguinte equação agregada foi obtida pelo teorema de Mathews:
26190 x12 + 26190 x13 + 26190 x14 + 47142 x 21 + 47142 x 23 + 47142 x 24 + 10185 x31
+ 10185 x32 + 10185 x34 + 581x41 + 581x 42 + 581x43 + 26190 y1 + 47142 y 2 + 10185 y 3
+ 581 y 4 = 84098
Observando a cota descrita para o limitante de Frobenius para o caso geral, como o
mdc(581,26190 = 1) e são os dois menores com essa característica, temos:
L* = 581 × 26290 − 581 − 26190 = 15189619
que é um número maior que o termo independente 84098, portanto nada se pode afirmar para
tal equação em termos de existência de solução, mas o número de restrições foi reduzido para
apenas uma equação.
Este problema com 4 vértices, com e sem agregação, foi resolvido utilizando o pacote
GLPK (GNU Linear Programming Kit) e a solução foi obtida no mesmo tempo computacional
de 0.0s.
Quando o número de vértices foi um pouco maior (oito vértices) o tempo para encontrar
a solução ótima no caso com agregação foi bem maior (4.2s) que no caso sem agregação (0.3s),
ou seja, não foi bom utilizar agregação. A utilização da agregação também não foi eficiente
com 10 vértices, pois o comportamento foi parecido.
Com 16 vértices, o resultado com agregação após cerca de 10 minutos não chegou a
nenhum resultado e foi encerrado a busca, pois o tempo já estava muito elevado em relação ao
tempo sem agregação, que utilizou 1.3s.
Assim, percebemos que a agregação de equações para restrições do tipo (3), que
tenham apenas coeficientes zeros e uns, não foi eficiente, tornando a busca por soluções mais
lenta.
Quando restrições que envolvam desigualdades na mesma direção no modelo são
substituídas por uma única restrição que é uma combinação linear das anteriores isso tem o
efeito de tornar o conjunto de soluções factível maior [5]. Isso pode acarretar em um tempo de
busca maior, como foi mostrado nos exemplos anteriores.
Entretanto, resolvemos fazer novos testes pensando que, em problemas como o TSP,
em geral, podem surgir outros tipos de restrições além das já apresentadas. Por exemplo,
existem problemas em que o caixeiro tem capacidade máxima de carregamento ou os vértices
802
têm pesos, indicando importância ou precedência. Assim, uma nova alternativa foi direcionar a
agregação para esse tipo de restrição, visto que para restrições com coeficientes zeros e uns as
agregações não foram bem sucedidas.
Considere que as seguintes restrições de capacidade foram impostas ao TSP:
2 x1 + 5 x 2 + 13 x3 + 12 x4 + 11x 5 + 10 x6 + 9 x7 + 10 x8 = 27
7 x1 + 10 x 2 + 10 x3 + 15 x4 + 21x5 + 10 x6 + 18 x7 + 26 x8 = 35
13 x1 + 8 x 2 + 9 x3 + 10 x4 + 17 x5 + 20 x6 + 11x7 + 5 x8 = 38
Tendo em vista um pré-processamento, pode-se verificar que o limitante de Frobenius
garante que há solução para algumas restrições acima, pois utilizando a cota descrita
anteriormente, temos:
L1 = 2 × 5 − 2 − 5 = 3 < 27 ⇒ Há solução!
L2 = 7 × 10 − 7 − 10 = 53 > 35 ⇒ Nada se pode afirmar.
L3 = 13 × 8 − 13 − 8 = 83 > 38 ⇒ Nada se pode afirmar.
Ao tentar resolver esse problema sem agregação, não foi possível encontrar solução em
20 minutos e a busca foi interrompida. Usando a agregação considerando o agrupamento das
duas primeiras restrições, obtivemos o seguinte sistema:
324 x1 + 465 x 2 + 473 x 3 + 702 x4 + 977 x5 + 470 x6 + 837 x7 + 1206 x 8 = 1637
13 x1 + 8 x 2 + 9 x3 + 10 x4 + 17 x5 + 20 x6 + 11x7 + 5 x8 = 38
Neste caso, a resposta foi obtida em 0.0 segundos, ou seja, um ganho de tempo
excelente com a agregação. Com a agregação das três restrições obteve-se:
119482x1 + 73793x 2 + 82967 x 3 + 92362x4 + 156799x 5 + 183790x6 + 101663x7 + 47036 x8 = 349945
que forneceu resposta em 1.0 segundos, um ganho também muito bom em comparação ao
conjunto de restrições não agregadas.
Considerando agora um novo conjunto de restrições impostas ao problema, como o
descrito a seguir:
3 x1 + 5 x 2 + 7 x3 + 11x 4 + 13 x5 + 37 x6 = 17
7 x1 + 8 x 2 + 6 x 3 + 5 x4 + 23 x5 + 54 x6 = 22
17 x1 + 13 x 2 + 21x3 + 8 x4 + 31x5 + 7 x6 = 47
23 x1 + 7 x 2 + 41x 3 + 13 x4 + 51x 5 + 37 x6 = 55
Novamente fazendo um pré-processamento, pode-se verificar que a cota do limitante de
Frobenius para as restrições anteriores será:
L1
L2
L3
L4
= 3 × 5 − 3 − 5 = 7 < 17 ⇒ Há solução!
= 5 × 6 − 5 − 6 = 19 < 22 ⇒ Há solução!
= 7 × 8 − 7 − 8 = 41 < 47 ⇒ Há solução!
= 7 × 13 − 7 − 13 = 71 > 55 ⇒ Nada se pode afirmar.
Agregando as quatro equações, teremos:
42700730 x1 + 13137153 x 2 + 75950759 x 3 + 24106275 x 4 + 94563978 x 5 + 68328039 x6
= 102225065
cuja solução foi encontrada em 1.3s.
Para um novo conjunto de restrições:
5 x1 + 6 x 2 + 7 x3 + 9 x4 = 8
7 x1 + 8 x 2 + 6 x 3 + 5 x4 = 22
17 x1 + 13 x 2 + 21x 3 + 8 x 4 = 47
23 x1 + 7 x 2 + 41x 3 + 13 x4 = 55
803
Analisando o Limitante de Frobenius para a primeira restrição, pode-se calcular
exatamente o limitante de Frobenius da seguinte forma:
 a   a + 1
a + 2
g (a , a + 1, a + 2 , a + 4 ) = (a + 1)  + 
+ 2

 −1⇒
4   4 
 4 
 5   5 + 1
5 + 2
g (5 ,6 ,7 ,9 ) = (5 + 1)  + 
+ 2

 −1⇒
4  4 
 4 
 5  6 
7 
g (5 ,6 ,7 ,9 ) = 6   +   + 2   − 1 = 6 + 1 + 2 − 1 = 8
4  4 
4 
Pode-se afirmar que não existe solução para o sistema, pois o termo independente é
igual ao limitante de Frobenius, portanto 8 é o maior inteiro que não pode ser escrito como
combinação linear não negativa dos coeficientes 5,6,7 e 9. Esse tipo de pré-processamento pode
ser bastante útil, pois evita a busca por uma solução inexistente.
Considerações Finais
A otimização do tempo de busca para muitos problemas computacionais é algo sempre
relevante. Diante disso, esse trabalho teve como enfoque a criação de uma metodologia visando
uma busca mais rápida de soluções para problemas de programação linear inteira, como o TSP.
A metodologia abordada consistiu em agrupar restrições com a utilização de conceitos
de agregação de equações Diofantinas, verificando o impacto desta agregação no tempo de
solução do problema, bem como na qualidade da solução e no gasto computacional. Percebeuse que a metodologia não funcionou bem para equações com coeficientes zeros e uns, tornando
a busca por solução mais lenta em quase todos os casos. Em contrapartida, ao analisar
restrições mais gerais, que geralmente são impostas nesses problemas, verificou-se que o tempo
de busca de solução foi bastante reduzido nos casos testados. Além disso foi proposta a
utilização de um pré-processamento baseado no limitante de Frobenius, visando uma melhora
no tempo de busca.
Os tempos computacionais mostraram que esta abordagem pode ser útil em alguns
casos particulares.
Referências
[1] J.L.R. Alfonsín, "The Diophantine Frobenius Problem", Oxford University Press, USA,
2005.
[2] D. A. Babayev e S. S. Mardanov, Sequential and simultaneous aggregation of
diophantine equations, Discrete Applied Mathematics, vol. 50, pp. 209-220, (1994).
[3] R. Diestel, "Graph Teory", Springer-Verlag, New York, 2000.
[4] A. A. Elimam e S.E. Elmaghraby, On the reduction method for integer linear programs,
II, Discrete Applied Mathematics, vol. 12, pp. 241-260, (1985).
[5] M. C. Goldbarg e H. P. L. Luna, "Otimização Combinatória e Programação Linear",
Elsevier, São Paulo, 2000.
[6] A. Khurana e K. G. Murty, How effective is aggregation for solving 0–1 models?,
Opsearch, vol. 49, pp. 78-85, 2012.
[7] E.L.Lawler e J.K.Lenstra, "The Traveling Salesman Problem", Wiley, Chichester, 1985.
[8] A. C. Muniz Neto, Como Fermat e Bézout podem salvar o dia, Eureka! Olimpíada
Brasileira de Matemática, vol. 12, n. 1, pp. 25-30, 2001.
804