Relaxação Lagrangeana – Prática

Em um post anterior, expliquei brevemente o conceito de relaxações, focando em relaxação lagrangeana. Hoje vamos apresentar uma heurística que encontra multiplicadores lagrangeanos.

Aplicaremos o algoritmo no problema da localização de instalações.

Algoritmo

O algoritmo mais conhecido para encontrar bons multiplicadores lagrangeanos é dado por Beasley [1], e é conhecido por método do subgradiente.

Geometricamente, se tivéssemos dois multiplicadores lagrangeanos, estes representariam pontos em um plano e os valores das soluções ótimas do dual lagrangeano para um desses pontos (multiplicadores) formariam curvas de níveis. O que o algoritmo faz é procurar um ponto com o valor mais próximo do da solução ótima primal e para isso anda em uma direção (gradiente) em que há melhoria dessa função.

Se não houver melhoras por um longo tempo, pode ser que o “passo” que estamos dando a cada iteração esteja muito grande e pode ser que haja uma solução melhor do meio desse passo. Por isso, vamos diminuímos gradativamente o passo, até que eventualmente este fique menor que um tamanho mínimo.

Onde a função Atualiza_multiplicadores é dada por:

Neste algoritmo é usado o valor de uma solução primal, que é obtida a partir da relaxação através de uma heurística.

Aplicação ao problema da Localização de Instalações

Vamos usar a relaxação das desigualdades que forçam os clientes a serem cobertos por pelo menos uma instalação (como descrito em um post anterior).

Heurística lagrangeana. Como estamos trabalhando com a versão sem restrição de capacidade, dado um conjunto de fábricas abertas é trivial encontrar a solução de melhor custo, bastando ligar cada cliente à instalação aberta mais barata. É essa heurística que usaremos para obter uma solução primal a partir de uma solução relaxada.

Multiplicadores lagrangeanos. Note que o algoritmo requer um conjunto de multiplicadores lagrangeanos inicial. No nosso caso, fizemos u_i = \frac{1}{n}, onde n é o número de desigualdades relaxadas.

Para os outros parâmetros do algoritmo usamos: \pi = 2, T_\pi = 0.2 e N_{stuck} = 30.

Fiz uma implementação em C++, tentado separar o problema (classe FacilityLocation implementando a classe virtual LagrangeanModel) do algoritmo (classe GradientMethod). Como de costume, o código está no github.

Resultados computacionais

Para testar o algoritmo, usei as instâncias do problema Capacitated Facility Location da OR-Library [3]. Como estamos lidando com a versão não restrita (uncapacitated), ignorei os dados de capacidade.

Há também este arquivo com os valores ótimos das soluções de forma que podemos observar a qualidade das soluções obtidas via relaxação empiricamente. A tabela a seguir contém o nome da instância, o número de instalações, o número de clientes, a distância percentual entre o ótimo e o melhor valor primal obtido (Gap), a distância percentual entre os melhores valores valores primal e dual (Gap DP) e finalmente o tempo.

Observamos que a solução ótima foi encontrada para boa parte das instâncias. O pior resultado foi para a instância capb, devido à dificuldade do algoritmo em encontrar bons multiplicadores lagrangeanos (note a distância entre os valores primal e dual).

Note que mesmo para instâncias grandes, provavelmente inviáveis de serem resolvidas de maneira exata, são resolvidas em menos de 6 segundos (processador i7 2.2GHz, sem paralelismo).

Conclusão

Embora tenhamos que lidar com uma formulação do problema para decidir quais restrições relaxar e obter o problema relaxado, geralmente para resolvê-lo não precisamos trabalhar com a formulação explicitamente (em geral resolver PL’s, principalmente de formulações grandes, não é muito rápido). Assim, dependendo da complexidade do problema resultante, a relaxação lagrangeana pode ser bastante eficiente.

Vimos que na prática as soluções obtidas via heurística lagrangeana podem ser muito boas. O principal problema é que a escolha dos parâmetros podem influenciar bastante a qualidade dessas soluções.

Eu já havia feito um trabalho sobre relaxação lagrangeana durante uma disciplina na faculdade, sobre um problema chamado Axis Parallel Minimum Stabbing Number Spanning Tree [2].

Referências

[1] J. E. Beasley – Modern Heuristics for Combinatorial Optmization Problem, Chapter 6 (Lagrangean Relaxation). Blackwell Scientific Publications, 1993.
[2] Relatório Programação Linear Inteira (MO420) – Guilherme Kunigami
[3] OR-Library

2 respostas a Relaxação Lagrangeana – Prática

  1. Oi Kunigami, valeu pelo post, está me ajudando muito.

    No algoritmo que descreve o método do subgradiente, na linha 4, onde tem f'(x*) >= zub não deveria ser f'(x*) >= zlb (limite inferior)?

    Da mesma forma na linha 10 onde tem f(|x) <= zlb não deveria ser f(|x) <= zub (limite superior)? E na linha 11 também, zub <-f(|x).

    Abraços.

  2. kunigami diz:

    Oi Fábio!

    Tem razão! Obrigado pela correção! Infelizmente a imagem veio de um pdf :( Vou ver se encontro o .tex original e atualizo aqui.

%d bloggers like this: