Problema de otimização

Problema de otimização, em matemática ou ciência da computação, é um problema de encontrar a melhor solução de todas as soluções viáveis. O problema de otimização pode ser dividido em duas categorias dependendo se as variáveis são continuas ou discretas. Um problema de otimização com variáveis discretas é conhecido como um problema de otimização combinatória. Em um problema de otimização combinatória, procuramos por um objeto como um inteiro, uma permutação ou grafo de um conjunto finito (ou possivelmente enumerável).

Problema da otimização contínua

A forma padrão de um problema de otimização contínuo é:

Minimiza X f(x)

Sujeito a:

• g_i(x) < 0, i = 1, ..., m
• h_i(x) = 0, i =1, ..., p

onde

• f(x): Rⁿ -> R é a função objetiva para ser minimizada sobre a variável x

• g_i(x) < 0 é chamada de restrições de desigualdade, e

• h_i(x) = 0 é chamada de restrições de igualdade

Pela convenção, a forma padrão define um problema de minimização. Um problema de maximização pode ser tratado pela negação da função objetiva.

Problema de otimização combinatória

Formalmente, um problema de otimização combinatória A é um quádruplo (I, f, m, g), onde

• I é um conjunto de instancias

• Dada uma instancia, x ∈ I, f(x) é um conjunto de soluções viáveis

• Dada uma instancia x e uma solução viável y de x, m(x,y) denota a medida de y, que é usualmente um real possível

• G é a função objetivo, e é tanto mínimo ou máximo.

O objetivo é então encontrar, por alguma instancia x , uma solução ideal, que é, y uma solução viável com m(x,y) = g{m(x,y’) | y’ e f(x)}.

Para cada problema de otimização combinatória, existe um problema de decisão correspondente que pergunta se existe uma solução viável por alguma medida particular m0.

Por exemplo, se existe um grafo G que contem vértices u e v, um problema de otimização pode “encontrar um caminho de u para v que usa os menores caminhos”. Este problema pode ter uma pergunta de, digamos, 4.

Um problema de decisão correspondente poderia ser “Existe um caminho de u para v que use 10 ou menos?” Este problema pode ser respondido com um “sim” ou um “não”.

Em um campo de algoritmos de aproximação, algoritmos são projetados para encontrar soluções quase ótimas para problemas difíceis.

A versão normal de decisão é então uma definição inadequada dos problemas uma vez que só especifica soluções aceitáveis. Mesmo que pudéssemos apresentar problemas de decisão adequados, o problema é mais naturalmente caracterizado como um problema de otimização.

Problema de otimização NP

Um problema de otimização NP (NPO) é um problema de otimização combinatória com as seguintes condições adicionais. Note que os polinômios referidos abaixo são funções do tamanho de entradas de respectivas funções, não o tamanho de algum conjunto implícito de instancias de entradas.

• O tamanho de todo solução viável y ∈ f(x) é polinomialmente delimitado em um tamanho de dada instancia x,

• As linguagens { x | x e I } e {(x,y)|y ∈ f(x) } pode ser reconhecido em tempo polinomial, e

• m é de tempo polinomial computável.

Isto implica que o problema de decisão correspondente é em NP. Em ciências da computação, problemas de otimização interessantes normalmente tem as propriedades acima referidas e são, portanto, problemas NPO. Um problema é adicionalmente chamado de problema otimização-P (PO), se existe um algoritmo que encontra soluções ideais em tempo polinomial. Muitas vezes quando se lida com a classe NPO, um está interessado em problemas de otimização para que as versões decisivas sejam NP-dificil. Note-se que as relações de dificuldade são sempre em relação a uma redução. Devido à conexão entre algoritmos de aproximação e problemas de otimização computacional, reduções que preservam a aproximação em alguma circunstancia são assuntos preferidos do que o usual Turing e as reduções de Karp. Um exemplo para tal redução poderia ser a redução de L. Por esta razão, problemas de otimização com versões decisivas de NP-completo não são necessariamente chamadas NPO-completo.

NPO é dividido entre as subclasses seguidas segundo sua aproximação:

• NPO(I): É igual a FPTAS. Contem o problema da Mochila.

• NPO(II): É igual a PTAS. Contem o problema de programação Makespan (Makespan scheduling problem).

• NPO(III): A classe de problemas NPO que tempo algoritmos em tempo polinomial que calcula soluções com um custo na maioria das vezes c vezes o custo ideal (para problemas de minimização) ou um custo a menos 1/c do custo ideal (para problemas de maximização). No livro de Hromkvic, excluído desta classe são todos os problemas NPO(II) salvos se P=NP. Sem a exclusão, é igual a APX. Contém MAX-SAT e a métrica TSP.

• NPO(IV): A classe dos problemas NPO com algoritmos de tempo polinomial aproximando a solução ideal por uma razão que é um polinômio em logaritmo de tamanho da entrada. No livro de Hromkovic, todos os problemas NPO(III) são excluídos desta classe, a mesma que P =NP.Contem o problema de cobertura de conjuntos.

• NPO(V): A classe de problemas NPO com algoritmos de tempo polinomial aproximando a solução ideal por uma razão delimitada pela função em n. No livro de Hromkovic, todos os problemas NPO(IV) são excluídos desta classe, a mesma que P = NP. Contem o problema de Max Clique e TSP.

Outra classe de interesse é NPOPB, NPO com funções de custo polinomial limitadas. Problemas com esta condição tem muitas propriedades desejáveis.

Referencias

1. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. p. 129.
2. Ausiello, Giorgio; et al. (2003), Complexity and Approximation (Corrected ed.), Springer
3. Hromkovic, Juraj (2002), Algorithmics for Hard Problems, Texts in Theoretical Computer Science (2nd ed.), Springer,
4. Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems, Royal Institute of Technology, Sweden,