Outer Approximation

O principal objetivo do método de Aproximação Externa (Outer Approximation - OA) é lidar com problemas que possuem variáveis complicadoras, que, quando temporariamente fixadas, resultam em um problema significativamente mais fácil de resolver.

Algumas suposições e modificações no MINLP são necessárias; e os conceitos do método de Aproximação Externa permitirão uma melhor visão sobre o design do problema mestre e do subproblema associado à decomposição de Benders.

Na maioria das aplicações de interesse considera-se que as funções objetivo e de restrição são lineares em , e que não há equações não lineares . Sob essas suposições, o problema torna-se:

Para possibilitar a aplicação do método, algumas suposições são feitas, como as funções e serem convexas e diferenciáveis. Considerando um fixo, um subproblema é associado a , que é um NLP mais fácil de ser resolvido:

Se for inviável, uma versão relaxada é resolvida:

Aqui, é um vetor de uns de tamanho adequado. Minimizar significa que a região relaxada de solução para é minimizada. Se , o subproblema NLP associado ao MINLP é inviável para .

O método OA proposto por Duran surge quando os subproblemas NLP e , e o problema mestre MILP, são resolvidos sucessivamente em um ciclo de iterações para gerar os pontos , de forma relaxada:

Mesmo com a relaxação no objetivo com a variável , para obter uma forma equivalente de MINLP em um MILP, uma aproximação de primeira ordem da série de Taylor em de e é realizada em cada iteração :

Dada uma solução ótima de subproblemas NLP convexos em , com pontos , obtém-se um problema mestre MILP relaxado de Aproximação Externa:

onde o conjunto é definido, em cada iteração , como

A solução de fornece um limite inferior válido para o problema . Este limite é não decrescente com o número de pontos de linearização . Uma interpretação geométrica é que a função objetiva convexa, dada uma quantidade finita de aproximações, será subestimada.

Considerando , a região viável convexa é superestimada com as linearizações . Para que essas linearizações sejam válidas no processo de resolução do problema, algumas condições devem ser impostas para adicionar um corte à região viável:

1. Se estiver estritamente dentro da região viável, então os cortes não devem ser introduzidos.

2. Se estiver fora da região viável, então o subproblema de viabilidade produz um corte.

3. Deve-se considerar no corte apenas as restrições ativas. Em outras palavras, se houver subproblemas inviáveis, o valor ótimo , dado pelo problema , deve ser satisfeito na igualdade para o lado esquerdo das restrições.