Relaxação Lagrangeana – Prática

Março 11, 2012

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

Anúncios

Introdução ao Drools Planner

Novembro 20, 2011

O Drools Planner é um framework Java para resolução de problemas de planejamento através de meta-heurísticas, voltado especialmente para problemas de grande porte e alta complexidade (um número grande de restrições), que inviabilizam uma abordagem exata.

Além de prover um framework que fatora partes comuns a essas meta-heurísticas, o que permite reuso de código, o grande atrativo do Drools Planner é sua integração com o sistema de regras do Drools, o Drools Expert, que permite incluir restrições através de uma linguagem de alto nível.

O Drools Planner também provê uma ferramenta de benchmark, possibilitando a comparação, através de gráficos, entre os diversos algoritmos implementados com parâmetros diferentes, de modo a se escolher aquele que mais se adequa ao problema em questão.

Atualmente o Drools Planner implementa apenas algoritmos de busca local, entre eles: busca tabu, simulated annealing e great deluge.

Nota: A versão do Drools descrita nesse post é a 5.3.0 Final. Vale ainda ressaltar que como o Drools Planner em particular está em um estágio inicial, a API ainda está mudando bastante. Portanto, parte do que está escrito aqui pode não fazer sentido para versões anteriores.

Conceitos Básicos

Vamos discutir agora as principais características do Drools Planner.

Interfaces a serem implementadas

Solução. A solução de um problema é uma classe que representa as possíveis soluções do problema e deve implementar a interface Solution. Nessa classe geralmente incluímos referências a todas as informações que podem ser utilizadas pelo algoritmo.

Vizinhos. Para implementar uma busca local precisamos gerar soluções vizinhas a partir de uma dada solução. Cada tipo de movimento para gerar uma solução vizinha deve implementar a interface Move.

Vizinhança. No Drools Planner existe o conceito de fábrica de movimentos que, dada uma solução S, gera um conjunto de Moves, que estarão disponíveis para o algoritmo utilizar. Uma fábrica de movimentos deve implementar a interface MoveFactory.

Avaliação de uma solução com Drools Expert

A grande sacada do Drools Planner é usar o Drools Expert para associar um valor numérico a uma solução. Basicamente, o Drools Expert é uma linguagem de programação baseada em regras. Existe o conceito de working memory, onde diversos objetos, denominados fatos, estão inseridos. Num arquivo .drl, definimos as regras.

Uma regra utiliza a seguinte sintaxe:

rule "Nome da regra"
when
    // Conjunto de condicionais
then
    // Ação a ser tomada (sintaxe Java)
end

Quando um dado conjunto de fatos passa a satisfazer as condições da regra, a ação definida é executada. A vantagem é que em geral restrições são bem fáceis de serem modeladas com regras.

A ideia é escrever um regra que seja satisfeita quando uma restrição é violada. A ação a ser tomada é basicamente somar uma pontuação proporcional à importância dessa restrição. O algoritmo tratará de minimizar essa pontuação através da busca local.

Entidades de Planejamento

No Drools 5.3.0 foram introduzidos conceitos como Planning facts, entities, variables e value range.

Planning fact. É uma classe de fatos que são usados para calcular a pontuação, mas não são modificados ao longo do algoritmo.

Planning entity. É uma classe de fatos que são usados para calcular a pontuação, mas podem ser modificados pelo algoritmo. Essa classe deve ser anotada com @ PlanningEntity.

Planning Variable. São os membros de uma planning entity que podem ser modificados pelo algoritmo. Os getters desses membros devem ser anotados com @PlanningVariable.

Planning Value Range. São os possíveis valores que uma dada planning variable pode assumir. Geralmente esses valores são os elementos de uma lista na classe representando uma solução e nesse caso o getter dessa planning variable também deve conter a anotação @ValueRangeFromSolutionProperty.

Mais informações no manual.

Heurísticas Construtivas

A definição das entidades de planejamento (planning entities) permitem automatizar a geração de uma solução inicial através de heurísticas construtivas padrões como First Fit e Best Fit.

É possível definir sua própria heurística para construir a solução inicial. Para isso, basta o algoritmo implementar a interface CustomSolverPhaseCommand.

Arquivo de Configuração

Um outro item essencial do Drools Planner é o arquivo de configuração. Esse arquivo é no formato XML e define diversas características do algoritmo. Vamos destacar algumas delas.

Estrutura básica do arquivo de configuração

Ambiente de execução

A propriedade environmentMode define o ambiente de execução em que o algoritmo executará. Isso afeta o nível das mensagens de log e a checagem ou não de assertivas. Alguns valores mais comuns dessa propriedade são: DEBUG, REPRODUCIBLE e PRODUCTION.

Para mais informações, consulte o manual.

Classes da solução e da entidade de planejamento

É preciso informar qual classe implementa a solução do problema e qual representa a entidade de planejamento através das propriedades solutionClass e planningEntityClass, respectivamente.

Arquivo de regras

Através da propriedade scoreDrl, informamos o caminho para o arquivo de regras do Drools Expert.

Definição do tipo de pontuação

É possível trabalhar com diferentes tipos de pontuação especificando a propriedade scoreDefinition. As principais são SIMPLE e HARD_AND_SOFT. O primeiro é simplesmente um inteiro e o segundo um par de inteiros, sendo que um representa a parte “hard” e a outra “soft”. Uma pontuação “hard” não nula representa uma solução inviável e portanto tem peso infinitamente maior do que a pontuação “soft”.

A ideia de ter uma pontuação “hard” é permitir que o algoritmo trabalhe com soluções inviáveis e dessa forma conseguir escapar de ótimos locais no espaço de soluções viáveis.

Critério de Parada

A propriedade termination define as condições de parada do algoritmo, como por exemplo tempo de execução, número de iterações sem melhoria da solução, valor de solução alcançado, etc. Para mais detalhes, consulte o manual.

Escolha da heurística construtiva

Através da propriedade constructionHeuristic podemos definir as heurísticas usadas para a construção da solução inicial. Como dito anteriormente, algumas delas são FIRST_FIT e BEST_FIT. Mais informações no manual.

Se você optou por implementar sua própria heurística, a propriedade customSolverPhase deve ser utilizada. Mais detalhes no manual.

Configuração da Busca Local

Há três propriedades principais que precisamos para configurar a busca local: selector, acceptor e forager.

Selector. Define quais fábricas de movimentos serão utilizadas

Acceptor. Define qual algoritmo utilizar, bem como possíveis parâmetros do algoritmo escolhido. Por exemplo, o seguinte trecho de configuração:

<acceptor>
  <completeSolutionTabuSize>
    100
  </completeSolutionTabuSize>
</acceptor>

especifica que usaremos uma busca tabu que possui um conjunto de soluções tabu de tamanho 100 (ou seja, guarda as últimas 100 soluções encontradas e não deixa o algoritmo voltar nelas).

Forager. Especifica a escolha do movimento. As fábricas de movimentos gerarão muitos movimentos a partir da solução corrente. A propriedade minimalAcceptedSelection define que apenas um subconjunto desses movimentos sejam analisados para melhorar a eficiência.

Já a propriedade pickEarlyType permite parar de analisar os vizinhos assim que encontrar um satisfazendo alguma condição (como por exemplo algum que tenha pontuação melhor que a solução corrente).

Para mais detalhes sobre essas três propriedades, consulte no manual.

Conclusão

Pelo que estudei do Drools Planner até agora, consigo ver as seguintes vantagens:

* Parte comum das meta-heurísticas já está implementada
* Sistema de regras é escalável
* Fácil adicionar novas restrições se não precisar mudar as entidades

Já as desvantagens:

* Debugar código Drools é mais difícil do que debugar código Java (principalmente a parte do “when“)
* Paradigma diferente (programação declarativa)


GRASP

Setembro 3, 2010

GRASP (Greedy Randomized Adaptive Search Procedures) é uma meta-heurística para problemas de otimização combinatória. Meta-heurística basicamente é uma heurística que resolve problemas genéricos, com algumas pequenas adaptações. Esse método foi originalmente desenvolvido pelo brasileiro Maurício Resende, que hoje é pesquisador no AT&T.

De maneira geral, o algoritmo consiste de duas fases: construção e busca local. Na fase de construção tenta-se construir uma solução viável com um método que é um pouco guloso e um pouco aleatório. A busca local consiste em explorar vizinhos de uma solução até encontrar uma solução ótima local. Essas duas fases são repetidas por um certo número de iterações. Intuitivamente, o algoritmo sorteia pontos no espaço de soluções, quase que aleatoriamente (não é totalmente aleatório devido ao fator guloso, que tende a sortear soluções de melhor custo). Aí a busca local faz o trabalho de achar o ótimo local a partir de cada um desses pontos. Observe que as iterações são independentes entre si.

Construção da solução inicial

Para ficar mais claro, vamos considerar o problema de encontrar o caminho Hamiltoniano de custo mínimo, ou seja, dado um conjunto de cidades, encontrar a ordem em que se deve visitá-las de forma a minimizar o custo total de se viajar de uma cidade para outra. Podemos enxergar esse problema como o problema de encontrar a permutação de menor custo de elementos. O custo de uma permutação é a soma das distâncias entre dois elementos adjacentes nela.

O algoritmo é basicamente o seguinte: fazemos n iterações. Na i-ésima iteração, decidimos qual elemento ocupará a i-ésima posição do vetor representando a permutação. Para cada i,

  1. Construímos uma lista restrita de candidatos (Restricted Candidate List RCL)
  2. Selecionamos um elemento ‘s’ da RLC aleatoriamente e inserimos ele na posição i
  3. Remova ‘s’ da lista de candidatos

A construção da RCL é a parte principal dessa fase. Primeiramente calculamos o aumento no custo que cada elemento da lista de candidatos causará se for inserido na i-ésima posição. No nosso caso isso é basicamente sua distância para o elemento (i-1). Salvamos qual foi o maior e o menor custo desses elementos, cmin e cmax, respectivamente. Aí inserimos na RCL apenas os elementos cujo custo c(e) satisfizerem

Onde é um parâmetro de controle. Se , só o elemento de menor custo será inserido na RCL enquanto que se , todos os elementos o serão. Observe que como o elemento da RCL é escolhido aleatoriamente, se só houver um elemento, não há espaço para aleatoriedade e o algoritmo fica puramente guloso. Por outro lado, se todos os elementos estão na RCL, qualquer elemento é igualmente possível de ser escolhido, o que torna o algoritmo puramente aleatorio. Assim, fornece um controle sobre o quão guloso ou aleatorio é essa construção.

Busca Local

Após construída a solução inicial, realizamos a busca local que consiste em andar por soluções adjacentes que melhorem o custo da solução. A escolha da vizinhança é crucial para a eficácia do algoritmo. No nosso problema, uma possível vizinhaça seria as soluções obtidas trocando-se dois elementos de posição.

Há duas estratégias para “caminhar” em uma busca local: o First Improving e o Best Improving. Na primeira, logo que encontramos uma solução vizinha que seja melhor do que a solução atual, damos o passo. Já na segunda, exploramos todos os possíveis vizinhos e damos o passo na direção daquele de melhor custo.

Busca local termina em ótimos locais.

Path Relinking

Uma técnica para complementar o algoritmo GRASP é chamada de Path Relinking. Ela consiste em guardar um conjunto limitado de soluções — de baixo custo e suficientemente diferentes entre si — encontradas no decorrer do GRASP, e é chamado de soluções de elite. Ao chegar no ótimo local após a busca, consideramos os caminhos para sair dessa solução e chegar até cada uma das soluções de elite. A esperança é de que existam boas soluções no meio desses caminhos.

Bibliografia

[1] Greedy Randomized Adaptive Search Procedures: Advances and Applications – Resende, Mauricio e Ribeiro, Celso. Handbook of Metaheuristics 2008.