Nos vários sectores de actividade surgem com frequência problemas de optimização que apresentam a particularidade de envolverem um número elevado mas finito de alternativas. Exemplos comuns são o escalonamento de operações em unidades fabris, o escalonamento de tripulações para prestação de serviços de transporte, a planificação de rotas de entregas, a localização de escolas e centros de prestação de cuidados de saúde ou a concepção de redes de telecomunicações.
Neste tipo de problemas é teoricamente possível enumerar todas as soluções e avaliar cada uma relativamente a um dado objectivo, previamente estabelecido. As que produzem o resultado mais favorável são consideradas óptimas. Contudo, do ponto de vista prático, é inviável a adopção desta estratégia para a resolução de problemas, uma vez que o número de soluções frequentemente cresce de forma incontrolável, com o tamanho do problema.
Ao longo das últimas cinco décadas tem sido realizado um vasto trabalho de investigação no sentido de desenvolver métodos de pesquisa óptimos que não exijam a análise explícita de cada alternativa. Com este trabalho de investigação estabeleceu-se, e tem vindo a evoluir, o campo da Optimização Combinatória (OC) e, conjuntamente, uma capacidade de resolver problemas do mundo real de dimensões crescentes.
Este apontamento introdutório, baseado em [Feo, Resende 1995] apresenta, de forma concisa, os aspectos mais relevantes do contexto em que surge a OC, bem como o seu objecto: os Problemas de Optimização Combinatória (POC).
2.1.2 Problemas de Optimização Combinatória
Um POC é um problema de optimização matemática com um conjunto de soluções admissíveis discreto. Na sua forma mais geral, pode ser enunciado do seguinte modo: dado
um conjunto discreto S e uma função f:S →ℜ, encontrar um elemento s*∈S para o qual
{
∈S}
= s s
s*) min f( )|
f( . (2.1)
Os elementos do conjunto S são denominados soluções admissíveis, enquanto o
conjunto em si é designado espaço de soluções ou espaço de decisão. À função f chama-se função
objectivo. Sem perda de generalidade, restringir-se-á a presente discussão a problemas de
Tipicamente, um POC não será formulado de forma tão geral. Antes, será disponibilizada uma caracterização não enumerativa do espaço de soluções e uma forma algorítmica de avaliar o valor da função objectivo para cada solução admissível [Thienel 1995]. Veja-se, como exemplo desta última, o caso particular de um POC com uma função objectivo linear, dada por coeficientes de peso relativos aos elementos de um conjunto base, que compõem as soluções do problema. Está-se, neste caso, perante um Problema de
Optimização Combinatória Linear, que, na sua forma mais geral, pode ser enunciado do seguinte
modo: dado um conjunto discreto E de "entidades fundamentais", um conjunto E
S ⊆2 de
subconjuntos de E , uma função c:E→ℜ e sendo, para cada conjunto F⊆ E,
( )
∑
( )
∈ = F F e e cc , encontrar um conjunto s*∈S para o qual
{
∈S}
= s s
s*) min c( )|
c( . (2.2)
É frequente e, num certo sentido, natural formular um POC como um Problema de
Optimização Inteira, no qual as soluções s∈S são descritas por vectores de variáveis inteiras
(tipicamente binárias) e S é descrito por um conjunto de restrições de igualdade e/ou desigualdade. Esta forma de descrição constitui, ela própria, um exemplo de caracterização não enumerativa do espaço de soluções.
2.1.3 Complexidade Computacional
Em princípio, um POC poderia ser resolvido por uma enumeração exaustiva do espaço de soluções, com o cálculo do valor da função objectivo para cada solução admissível. No entanto, o facto, já apontado, de que o número de soluções admissíveis pode crescer de forma incontrolável com a dimensão do problema torna o método de enumeração impraticável na generalidade das situações. Com efeito, existem POC para os quais apenas são conhecidos algoritmos de resolução cujo tempo de cálculo aumenta de forma incontrolável (no sentido que se precisará de seguida) com o tamanho do problema (traduzindo, assim, o seu carácter combinatório "explosivo").
A teoria da Complexidade Computacional (ver, por exemplo, [Papadimitriou, Steiglitz 1982] ou [Nemhauser, Wolsey 1989]) disponibiliza um enquadramento adequado para o conjunto de questões associadas à "eficiência" dos algoritmos. Faz-se, aqui, apenas uma breve introdução às ideias fundamentais desta teoria e às suas implicações práticas, com base nas referências atrás indicadas.
A medida de desempenho (em termos de eficiência) mais utilizada para algoritmos baseia-se no tempo dispendido até à determinação da solução final (óptima). Para a tornar independente de particularidades de computadores, como a velocidade ou o conjunto de instruções, ou de linguagens de programação, é frequente esta medida ser referida ao número de passos algorítmicos elementares (operações aritméticas, comparações, etc.) de execução do algoritmo num computador hipotético.
Este número de passos varia, em geral, com a entrada ("input") do algoritmo, ou seja, com a instância do problema que se pretende resolver. Uma instância (ou seja, uma concretização numérica) de um POC consistirá habitualmente de um objecto combinatório como um grafo, um conjunto de valores inteiros (organizados em vectores ou matrizes) ou outros. Para tratamento por computador, este objecto deverá ser codificado, ou representado, como uma sequência de símbolos sobre um alfabeto pré-definido (de que bits e ASCII constituem exemplos). O tamanho da entrada de um algoritmo, logo, de uma instância, será o comprimento dessa sequência de símbolos, ou seja, o número de símbolos que a compõem.
A complexidade de um algoritmo, para um tamanho de instância determinado, é o desempenho mais desfavorável do algoritmo ("worst-case"), para uma qualquer instância desse tamanho, e que, em geral, será função desse tamanho. São considerados particularmente úteis os algoritmos polinomiais, ou seja, aqueles cuja complexidade é uma função polinomial do tamanho da instância. Apresentam igual interesse os algoritmos cuja complexidade, não sendo polinomial, seja limitada polinomialmente. Os algoritmos cuja complexidade não é limitada polinomialmente são designados exponenciais.
Apenas são conhecidos algoritmos exponenciais para a resolução dos POC pertencentes à classe dos problemas NP-difíceis ("NP-hard"). Para a introdução deste conceito é importante estabelecer em primeiro lugar a relação entre Problemas de Optimização (PO) e
Problemas de Decisão (PD). Um PD é um problema que exige uma resposta exclusivamente do
tipo sim-ou-não. O PD correspondente à forma mais geral do POC, apresentada em (2.1), seria:
para um determinado valor z, existe uma solução s∈S tal que f
( )
s ≤z?Existindo um algoritmo polinomial para resolver um PD, é possível resolver em tempo polinomial o PO correspondente, verificando-se igualmente o inverso. Como tal, os conceitos seguintes, introduzidos na área da Decisão, são de imediata aplicação na área da Optimização.
A classe P engloba os problemas para os quais se conhecem algoritmos que, para todas as instâncias do problema, produzem uma solução em tempo polinomial. A classe NP engloba os problemas para os quais é possível, em tempo polinomial, comprovar a
Um problema de decisão PD1 é transformável em tempo polinomial num problema de
decisão PD2 se para qualquer instância x de PD1 for possível construir em tempo polinomial
uma instância y de PD2, tal que a y corresponda uma resposta sim se e só se a x corresponder
uma resposta sim.
Um PD diz-se NP-completo se pertence a NP e todos os problemas em NP podem nele ser transformados em tempo polinomial. Os problemas NP-completos apresentam algumas propriedades interessantes:
1. São problemas de elevada dificuldade computacional, não sendo conhecidos algoritmos polinomiais para nenhum deles.
2. Por outro lado, não se encontra provada a inexistência de algoritmos polinomiais para estes problemas.
3. A existir um algoritmo polinomial para um problema NP-completo, existiriam algoritmos polinomiais para todos os outros.
4. Inversamente, a demonstração de inexistência de um algoritmo polinomial para um dos problemas NP-completos, implicaria a inexistência de algoritmos polinomiais para todos os outros.
Um PD diz-se NP-difícil se todos os problemas em NP podem nele ser transformados em tempo polinomial, mas é desconhecido se esse problema pertence a NP. Os PO cujos PD correspondentes são NP-completos designam-se igualmente NP-difíceis (com efeito não pertencem a NP, uma vez que não são problemas de decisão). Muitos dos problemas práticos de interesse na área da Investigação Operacional, e em particular a grande maioria dos POC, são NP-difíceis [Lenstra et al. 1982], o que contribui decisivamente para a relevância da teoria da Complexidade Computacional nesta área.
Em termos práticos, poder-se-ia dizer que estes problemas, devido ao seu carácter combinatório, são intrinsecamente difíceis, e que os métodos de resolução não conseguem ultrapassar essa dificuldade. Esta perspectiva tem sentido, uma vez que, na prática, existem problemas difíceis cuja resolução não deverá naturalmente ser simples. Refira-se, no entanto, que para a avaliação prática da eficiência dos algoritmos, esta teoria é algo limitada, uma vez que se baseia numa análise do desempenho mais desfavorável (análise de "worst-case"), não tendo em conta que alguns algoritmos exponenciais podem apresentar um excelente desempenho em determinadas classes de instâncias (o que tem conduzido a outros tipos de análise, de carácter probabilístico).
A necessidade prática de resolver estes problemas tem levado a que, em alternativa aos algoritmos exactos - algoritmos que determinam a solução óptima - se tenham vindo a desenvolver outras abordagens de resolução deste tipo de problemas, que visam reduzir a carga computacional inerente à sua resolução. Estas abordagens podem apresentar diferentes características relativamente à qualidade da solução e ao tempo de resolução [Papadimitriou, Steiglitz 1982]:
1. Algoritmos de aproximação. Estes algoritmos produzem soluções que não são óptimas, mas relativamente às quais se possui a garantia de um limiar de afastamento em relação ao óptimo.
2. Algoritmos probabilísticos. Em alguns casos é possível desenvolver algoritmos que apresentam, em geral, um bom desempenho - aos níveis da qualidade da solução encontrada e do tempo consumido - assumindo determinadas distribuições de probabilidade para as instâncias do problema.
3. Casos especiais. Alguns casos particulares de problemas NP-difíceis podem ser de fácil resolução. Nestas situações, o facto de o problema geral ser NP-difícil é relativamente irrelevante.
4. Algoritmos exponenciais. Alguns destes algoritmos podem revelar-se de interesse prático, como pode ser o caso de algoritmos pseudo-polinomiais (algoritmos polinomiais em ordem ao tamanho da instância e ao maior inteiro da instância) ou algoritmos em média sub-exponenciais (não-polinomiais, mas com
complexidade inferior a 2nε,ε>0) mas que encontram sempre a solução
óptima. A sua aplicação a instâncias de dimensão reduzida apresenta igualmente interesse prático.
5. Pesquisa local. Um dos métodos com maior sucesso na resolução de POC difíceis é o análogo discreto do procedimento de "hill climbing", designado pesquisa local, que será tratado pormenorizadamente em parte posterior deste texto.
6. Heurísticas. Qualquer das abordagens anteriores, na ausência de uma garantia formal de desempenho, pode ser considerada uma heurística. Embora não garantindo a obtenção da solução óptima, as heurísticas produzem, de uma forma eficiente, soluções satisfatórias (soluções próximas do óptimo ou significativamente melhores do que as obtidas por métodos alternativos). Apesar de poderem ser, nalguns casos, pouco satisfatórias do ponto de vista matemático, estas abordagens são seguramente de interesse em situação práticas.
Uma outra abordagem, cuja aplicação à resolução de POC se tem revestido de algum sucesso prático, é a Programação Lógica por Restrições ("Constraint Logic Programming"). Esta abordagem surgiu na área da Inteligência Artificial como extensão, para resolução de POC, das linguagens de programação baseadas em lógica [Mackworth 1977]. O problema é modelado como um Problema de Satisfação de Restrições, através de linguagens declarativas para a descrição das restrições, utilizando uma variedade de formas algébricas e lógicas. As técnicas utilizadas visam reduzir a dimensão do espaço de pesquisa, aplicando restrições que condicionam a ordem em que se realiza a selecção das variáveis e a atribuição de valores a cada variável, numa pesquisa tipicamente em árvore. Em [Gervet 1998] são apontadas as principais tendências de evolução nesta área, com referências que disponibilizam um tratamento mais pormenorizado, não enquadrável no âmbito do presente texto.