Neste post vamos comentar brevemente sobre relaxações de formulações lineares inteiras e focar especialmente em relaxações lagrangeanas. Depois, vamos demonstrar a aplicação dessa técnica no problema da localização de instalações (facility location). A menos que dito o contrário, estamos falando de problemas de minimização.
Relaxações
Em programação linear inteira, usamos o termo relaxação para indicar que algumas das restrições do problema original foram relaxadas. Provavelmente o exemplo mais conhecido de relaxação é o da relaxação linear. Nesse caso em particular, removemos as restrições de integralidade do modelo.
Mais formalmente, se tivermos uma formulação representada por
sendo o conjunto de pontos que satisfazem as restrições dessa formulação,
a função objetivo e
o valor da solução ótima. Dizemos que uma formulação
, dada por
é uma relaxação se todo ponto de está em
, ou seja
e se
para
.
Note que devido a essas propriedades, a solução ótima da relaxação é um limitante dual (ou seja, no nosso caso é um limite inferior e superior no de maximização) para a formulação original ou seja, . Limitantes duais podem ser utilizados, por exemplo, para melhorar o desempenho do algoritmo de Branch and Bound.
A vantagem de se usar relaxações é que em certos casos elas são mais fáceis de serem resolvidas. Por exemplo, as relaxações lineares podem ser resolvidas em tempo polinomial, enquanto a versão restrita a inteiros, em geral, é NP-difícil.
Podemos também relaxar uma formulação removendo algumas de suas restrições. Note, entretanto, que quanto mais relaxamos a formulação pior tende a ser a qualidade do limitante dual (considere o caso extremo onde removemos todas as desigualdades do modelo: não deixa de ser uma relaxação, mas o limitante dual obtido não serve para nada).
O ideal é que encontremos uma relaxação fácil de resolver e que dê limitantes duais de qualidade, ou seja, bem próximos do valor ótimo da formulação original.
Relaxação Lagrangeana
Existe uma técnica denominada relaxação lagrangeana [1], que consiste em remover algumas das restrições da formulação original, mas tenta embutir essas desigualdades na função objetivo. A ideia é penalizar a função objetivo quando as restrições removidas forem violadas. O “peso” dessas penalidades é controlado por coeficientes chamados multiplicadores lagrangeanos.
Em termos de matemáticos, suponha que tenhamos uma formulação com restrições e
variáveis:
Sujeito a
Onde representa as desigualdades que queremos relaxar e
as desigualdades que vamos manter. A relaxação lagrangeana é então dada por
Sujeito a
Onde é um vetor representando os multiplicadores lagrangeanos (um por cada desigualdade removida). Por exemplo, considere a desigualdade
que será removida:
Ao remover (11), o seguinte fator é subtraído da função objetivo
(1)
Note que quanto mais “violada” a desigualdade estiver, mais negativo o termo (1) vai ficar. Como a função é de minimização e estamos subtraindo, intuitivamente a solução ótima para o problema tenderá a não violar as desigualdades, melhorando o resultado do limitante dual.
Escolhe-se remover as desigualdades de forma que o problema resultante seja mais fácil resolver para um valor fixo de multiplicadores lagrangeanos. Porém, agora temos que resolver um outro problema: encontrar um conjunto de multiplicadores lagrangeanos que minimize
.
Aplicação ao problema da localização de instalações
O problema da localização de instalações é bastante estudado na literatura. Uma de minhas iniciações científicas consistia em estudar algoritmos aproximados para esse problema.
Basicamente temos um grafo bipartido onde uma partição corresponde ao conjunto de clientes e a outra ao conjunto de fábricas/instalações
. Cada cliente
pode ser potencialmente atendido pela fábrica
, a custo um
. Além disso, paga-se um custo
por abrir a fábrica
, dado por
. O objetivo é atender todos os clientes com o menor custo.
Vamos apresentar uma formulação linear inteira para esse problema. Seja uma variável binária que vale 1 sse o cliente
é atendido pela fábrica
e a variável
uma variável binária que vale 1 sse a fábrica
foi aberta. Temos a seguinte formulação:
Sujeito a
A desigualdade (2) diz que cada cliente deve ser atendido por pelo menos uma fábrica e a desigualdade (3), que uma fábrica deve estar aberta para que possa atender a algum cliente.
Essa é uma formulação bem simples e temos basicamente dois grupos de desigualdades. Vamos tentar relaxar o grupo de desigualdades indicado por (2). Teremos:
Sujeito a
Com um pouco de álgebra, é possível “fatorar” o somatório da função objetivo:
Como o termo é constante, podemos resolver o problema sem ele e depois somá-lo ao valor da solução obtida. Além disso, note que cada fábrica contribui de maneira independente à função objetivo e em cada restrição só aparecem variáveis associadas a uma dada fábrica.
Desta forma, podemos decompor essa formulação por cada fábrica :
Sujeito a:
Cada um desses problemas pode ser resolvido por inspeção. Seja . Vamos considerar duas possibilidades. Se fizermos
, não atenderemos nenhum cliente, levando a uma solução de custo 0. Se
, só compensa atender aos clientes com
. Assim, o custo ótimo dessa formulação é:
A outra alternativa consiste em relaxar a desigualdade (3). Nesse caso, depois de alguma álgebra, teremos:
Sujeito a:
Note que como não há restrições misturando e
, podemos resolver o modelo para cada tipo de variável separadamente. No caso da variável
, como
e
, não compensa abrir fábrica nenhuma. No caso de
, podemos resolver de maneira independente para cada
, por inspeção. Seja
. Se
, podemos fazer
. Caso contrário
, exceto no caso em que
para todo
. Nesse caso, devido à restrição (25), temos que fazer
, onde
.
Temos duas formulações que podem ser facilmente resolvidas. Entretanto, devemos levar em conta qual possui a formulação mais forte. Em outras palavras, dado e
, queremos o limitante dual que mais se aproxima de
. Entretanto, não sei dizer qual das duas relaxações apresentadas é a mais forte.
Conclusão
A relaxação Lagrangeana é uma técnica poderosa para se obter limitantes duais de problemas combinatórios que podem ser modelados como programas lineares inteiros. Esses limitantes podem ser usados na tentativa de melhorar o desempenho de algoritmos branch-and-bound.
Além do mais, para certos problemas, existe a possibilidade de ajustar a solução obtida via relaxação de modo a obter uma solução viável para o problema original, esperando que a qualidade da solução não seja muito pior.
Esse post apresentou a teoria por trás da relaxação lagrangeana. Num próximo post vou apresentar uma heurística que visa encontrar bons multiplicadores lagrangeanos.
Referências
[1] The Lagrangian relaxation method for solving integer programming problems – M.L. Fisher Management Science, 1981.