O uso das relaxações lagrangeana e surrogate em problemas de programação
inteira
1. Introdução
Problemas de otimização discreta são aqueles nos quais pelo menos um
subconjunto das variáveis de decisão deve assumir valores discretos em
intervalos pré-definidos. Esta classe inclui os problemas de otimização
combinatória, nos quais a solução ótima representa uma das combinações
possíveis dos valores das variáveis de decisão. Alguns dos problemas acima
podem ser formulados como Problemas de Programação Inteira, que em geral são
muito mais difíceis de serem resolvidos que os problemas de programação linear.
Seja o seguinte problema de programação inteira:
Na formulação acima x é o vetor de variáveis de decisão, c o vetor de custos, A
e D são matrizes de coeficientes tecnológicos e b e e são vetores de
disponibilidade de recursos.Não será utilizada notação especial para distinguir
vetores coluna ou linha. Todos os produtos vetoriais são produtos interiores no
sentido usual e as operações são tomadas como garantidas pelas dimensões de
vetores e matrizes correspondentes. Assumiremos que Ax£b são as restrições que
complicam a solução do problema (P), no sentido que o problema (P) pode ser
resolvido mais facilmente caso sejam removidas estas restrições.
Uma estratégia para resolver (P) consiste em resolver uma seqüência de
problemas "fáceis" obtidos a partir de relaxações do problema
original; com a solução de tais problemas procura-se obter limites para o valor
da solução ótima de (P). Foi neste contexto que as diferentes relaxações foram
desenvolvidas ao longo do tempo. Assumiremos, sem perda de generalidade, que
(P) é um problema viável e que o conjunto de soluções viáveis de cada problema
relaxado obtido a partir de (P) é um conjunto finito.
Nemhauser & Wolsey (1988) definem uma relaxação do problema (P) como um
problema de otimização, (RP), que possui as seguintes propriedades: (i) o
conjunto de soluções viáveis de (P) é um subconjunto das soluções viáveis de
(RP), e (ii) o valor da função objetivo do problema (P) não é menor que o
correspondente valor de (RP), isto é, v(RP) £ v(P) (para problemas de
minimização).
Uma relaxação usual dos problemas inteiros é a relaxação de programação linear,
que consiste em relaxar as condições de integralidade das variáveis de decisão.
Esta relaxação será chamada de RLP (Relaxação Linear de P) e o valor de sua
solução ótima será denotado por v(RLP). Uma das aplicações da relaxação de
programação linear é no desenvolvimento de algoritmos branch and boundpara a
solução do problema inteiro. Outras relaxações desenvolvidas para problemas de
programação inteira incluem as relaxações Lagrangeana, surrogate e combinadas
Lagrangeana-surrogate.
Neste trabalho é apresentada uma revisão bibliográfica destas relaxações, dos
métodos de solução para os duais correspondentes e das relações teóricas
existentes entre os mesmos. Será dada ênfase especial à relaxação surrogate e a
relaxações combinadas Lagrangeana-surrogate, por serem essas relaxações menos
conhecidas que a relaxação Lagrangeana. Finalizaremos o trabalho ilustrando a
obtenção de uma relaxação combinada Lagrangeana-surrogate para um problema de
localização hierárquico com restrições de cobertura.
Um estudo teórico das relaxações Lagrangeana e surrogate sob a ótica da
dualidade geral pode ser encontrado em Nieuwenhuizen (1999). Recentemente Li
(1999) apresentou o método da P-norma surrogate para resolver problemas de
programação inteira. A principal desvantagem deste método é que o problema
surrogate a ser resolvido é um problema altamente não linear, fato que
dificulta sua implementação computacional. Resultados empíricos relativos ao
uso das relaxações Lagrangeana, surrogate e combinada Lagrangeana surrogate
para um problema de localização hierárquico de máxima cobertura podem ser
encontrados em Espejo (2001) e Espejo et al. (2003).
2. A Relaxação Lagrangeana: Teoria e Aplicações
Held & Karp (1970), que utilizaram um método Lagrangeano para resolver o
problema do caixeiro viajante, foram precursores do uso deste método; Geoffrion
(1974) deu ao mesmo o nome de Relaxação Lagrangeana (ver Fisher, 1981).
A lista de aplicações da relaxação Lagrangeana é muito extensa. Tais aplicações
incluem o problema do caixeiro viajante, problemas de localização, o problema
de atribuição generalizado, problemas de recobrimento e particionamento de
conjuntos e problemas de roteamento, entre outros. Algumas aplicações da
relaxação Lagrangeana podem ser encontradas, por exemplo, no artigo de
Sridharan (1995), no livro de Bazaraa et al. (1993) e no capítulo escrito por
Beasley (1993) para o livro editado por Reeves. Entre as aplicações recentes da
relaxação Lagrangeana estão, por exemplo, as de Galvão et al. (2000, 2002) e
Fumero (2001). A relaxação Lagrangeana pode ser utilizada para fornecer limites
em algoritmos branch and bound, constituindo-se em uma alternativa ao uso da
relaxação de programação linear.
Uma relaxação Lagrangeana de (P) é obtida multiplicando o conjunto de
restrições Ax£b por um vetor u de multiplicadores de Lagrange de sinal
apropriado, adicionando-se o produto à função objetivo. A relaxação Lagrangeana
(Pu) do problema (P) é dada por:
Observe-se que o problema Lagrangeano é um problema em x, resolvido para um
dado vetor fixo u. Neste caso devemos escolher u ³ 0 para garantir que v(Pu)
seja um limite inferior para (P). Caso as restrições sejam da forma Ax£b os
multiplicadores devem ser não-positivos para garantir que v(Pu) £ v(P).
Finalmente, se Ax = b o sinal de ué irrestrito.
A qualidade do limite gerado por (Pu) depende do valor de u. O problema central
na obtenção de bons limites através desta relaxação é encontrar um conjunto de
multiplicadores uque resolve o Dual Lagrangeano (Du):
Em geral não se pode garantir a obtenção de um vetor u tal que v(Du) = v(P).
Uma solução ótima para (P) é obtida através da relaxação Lagrangeana quando
duas condições são satisfeitas simultaneamente: (i) a solução da relaxação
Lagrangeana é viável no problema (P), isto é, (Ax* ' b) £ 0, onde x* é a
solução ótima de (Pu) para u = u*; (ii) são satisfeitas as condições de folgas
complementares dadas por u*(Ax* ' b) = 0 (Greenberg & Pierskalla, 1970).
Observe-se que o fato de a solução ótima Lagrangeana x* ser viável para o
problema (P) não é suficiente para garantir que tal solução será ótima para
(P).
Fisher (1981) e Parker & Rardin (1988) provaram que v(Pu) é uma função
linear por partes, contínua e côncava, mas geralmente não diferenciável no
ponto ótimo. O fato de uma função ser côncava implica que um ótimo local é um
ótimo global. Esta propriedade da relaxação Lagrangeana faz com que ela seja
uma proposta atraente como estratégia para obter limites da solução de (P).
3. A Relaxação Surrogate
A relaxação surrogate consiste em reduzir algumas restrições do problema
original (P) a uma só restrição, denominada de restrição surrogate; sua função
é servir como substituta dessas restrições. A restrição surrogate é definida
como uma combinação linear não negativa de algumas restrições do problema em
estudo, onde pelo menos uma das restrições tem um peso positivo (Glover, 1965).
Desde sua introdução por Glover a relaxação surrogate tem sido proposta por
vários autores para uso na solução de problemas não convexos, especialmente em
problemas de programação inteira. Um tratamento teórico abrangente da dualidade
surrogate em programação matemática é dado por Greenberg & Pierskalla
(1970). Eles estabeleceram alguns resultados importantes para a construção da
melhor restrição surrogate e mostraram que isto implica na maximização de uma
função quase-côncava (para definição de função quase-côncava ver por exemplo
Bazaraa et al., 1993), ainda que possivelmente não contínua. Isso garante que
qualquer ótimo local é um ótimo global (sem considerar intervalos onde a função
é constante). Glover (1975) resumiu esses resultados e apresentou um tratamento
unificado da teoria da dualidade surrogate. O problema do gap surrogate foi
estudado por Glover (1975) e por Greenberg & Pierskalla (1970), que foram
os primeiros a demonstrar que o gap dual do enfoque surrogate é igual ou menor
que o gap dual do enfoque Lagrangeano; a relaxação Lagrangeana é denominada de
função de penalidade Lagrangeana no trabalho de Greenberg e Pierskalla. Um
estudo da relação entre o dual surrogate e o dual Lagrangeano no caso de
problemas inteiros foi feito por Karwan & Rardin (1979).
Considerando w³ 0 e w¹0 pode-se então escrever o Problema Surrogate de (P),
(Pw), como:
Como (Pw) é uma relaxação de (P) com w não negativo, v(Pw) não pode exceder o
valor ótimo da função objetivo de (P) (em problemas de minimização) e sua
aproximação a este valor será tanto melhor quanto w(Ax ' b) £ 0 seja uma melhor
representação das restrições Ax £ b. Observe-se que v(P0) £ v(Pw) para todo
w ¹ 0; desta maneira zero pode ser excluído como possível valor para w. Também
se pode observar que para qualquer k > 0, v(Pkw) = v(Pw); qualquer normalização
do vetor w é portanto possível. Greenberg & Pierskalla (1970) provaram que
para obter uma solução ótima para (P) através da relaxação surrogate não é
necessário que sejam satisfeitas as condições de folgas complementares; isto é,
qualquer solução ótima para o problema surrogate que seja viável para o
problema original é automaticamente ótima para o mesmo (ver também Glover,
1975).
O problema de escolher um w que melhore a proximidade de (Pw) a (P) implica na
escolha do multiplicador w que maximiza o valor do problema surrogate
correspondente. Isto motiva a seguinte definição do dual surrogate:
Glover (1975) dá as condições que devem ser satisfeitas para garantir a solução
ótima tanto do dual surrogate quanto do problema original. Essas condições são:
(i) O vetor de multiplicadores surrogate w deve ser não negativo; (ii) x é
solução ótima para o problema surrogate; (iii) x é viável para o problema
original. Tal como no dual Lagrangeano, não se pode garantir a obtenção de um
vetor w tal que v(Dw) = v(P).
Aplicações da Relaxação Surrogate
Quando comparadas com as da relaxação Lagrangeana, as aplicações da relaxação
surrogate não são tão variadas. A dificuldade de se resolver os problemas
resultantes da relaxação surrogate, que em muitos casos se reduzem a problemas
da mochila, pode ser uma das causas.
Na literatura encontram-se, entre outras, as seguintes aplicações da relaxação
surrogate. O uso das relaxações Lagrangeana e surrogate na decomposição de
Benders foi publicado por Rardin & Unger (1976) e Holmberg (1994). Na área
da programação não linear temos os trabalhos de Dinkel & Kochenberger
(1978) e Chen et al. (1998). Uma abordagem surrogate para problemas na forma do
problema da mochila foi realizada por Karwan & Rardin (1984) e Gavish &
Pirkul (1985). O problema de recobrimento de conjuntos foi resolvido,
utilizando uma heurística surrogate, por Lorena & Lopez (1994). Lorena
& Narciso (1996) utilizaram a relaxação surrogate para resolver o problema
de atribuição generalizado. Esta relaxação foi também usada na busca de limites
inferiores para a solução do problema de programação de tarefas, onde várias
máquinas competem pelo uso comum de um único buffer local (Khosla, 1995). Uma
das heurísticas de Galvão et al. (2000) utiliza a relaxação surrogate para
resolver o problema de localização de máxima cobertura. Finalmente, a relaxação
surrogate é uma das relaxações usadas por Espejo et al. (2003) para obter
limites superiores para o problema de localização hierárquico de máxima
cobertura.
4. Relaxações Combinadas Lagrangeana-Surrogate
Apresentamos a seguir duas relaxações que são obtidas aplicando simultaneamente
as relaxações Lagrangeana e surrogate a um dado problema inteiro.
4.1 A Relaxação Lagrangeana/Surrogate
Esta relaxação foi desenvolvida por Lorena & Senne (1996). O procedimento
utilizado pelos autores para criar este tipo de relaxação é dado a seguir.
1) Usando um vetor não negativo de multiplicadores surrogate, w, obter a
relaxação surrogate do problema (P):
2) Usando o multiplicador escalar não negativo, t, fazer uma relaxação
Lagrangeana da restrição (unidimensional) surrogate do problema (Pw). Obtém-se:
O dual do problema é dado por
Observe-se que este problema pode ser expresso como sendo o dual Lagrangeano
(Du) do problema (P), onde u=tw.
Aplicações do uso da relaxação Lagrangeana/surrogate podem ser encontrados em
Lorena & Senne (1996), que utilizaram este tipo de relaxação para resolver
um problema de localização não capacitado, e em Narciso & Lorena (1999),
para resolver o problema de alocação generalizado.
4.2 A Relaxação Combinada Lagrangeana-Surrogate
A criação de uma relaxação combinada Lagrangeana-surrogate do problema (P) foi
proposta por Greenberg & Pierskalla (1970). Os autores propuseram dualizar
um conjunto de restrições na função objetivo e, com outro conjunto de
restrições, formar uma restrição surrogate. Segundo esta proposta poderíamos
obter, por exemplo, duas relaxações Lagrangeana-surrogate combinadas para o
problema (P): (i) dualizar de forma Lagrangeana o conjunto de restrições Ax£b e
formar uma restrição surrogate com as restrições Dx £ e; (ii) particionar em
dois subconjuntos as restrições Ax£b; dualizar de forma Lagrangeana um desses
subconjuntos e com o outro formar uma restrição surrogate.
Glover (1975), seguindo esta mesma linha de pesquisa, definiu formalmente a
relaxação combinada Lagrangeana-surrogate e apresentou o primeiro
desenvolvimento teórico para este tipo de relaxação. A definição de Glover
difere da proposta de Greenberg & Pierskalla (1970), pois Glover utiliza o
mesmo conjunto restrições para formar a relaxação combinada Lagrangeana-
surrogate. A relaxação combinada Lagrangeana-surrogate pode ser obtida da
seguinte maneira (ver John & Kochenberger, 1988):
1) Considerar um vetor não negativo de multiplicadores surrogate, w, e formar a
restrição surrogate w(Ax-b)£0.Adicionar esta restrição ao problema (P) obtendo
É claro que v(P) = v(PSw), pois (Ax-b)£0 é uma restrição redundante em (P).
2) A seguir dualizar de forma Lagrangeana, com u ³ 0, o conjunto de restrições
Ax£ b do problema (PSw), formando o seguinte problema combinado Lagrangeano-
surrogate:
O melhor valor para o limite inferior derivado desta relaxação é obtido
resolvendo o seguinte problema dual:
v<formula/> é uma função côncava de u para w fixo e
quase-côncava de w para u fixo, ver Karwan & Rardin (1980). Os autores
provaram com um contra-exemplo que v<formula/>, como
função de u e w, perde a quase-concavidade. O fato de v
não ser uma função quase-côncava dificulta o desenvolvimento de
métodos de busca dos multiplicadores ótimos.
5. A Busca de Multiplicadores Ótimos
O problema crítico no uso efetivo das relaxações é a derivação de um bom
conjunto de multiplicadores para os problemas duais correspondentes. As
características dos duais das relaxações determinam se existem bons
procedimentos de busca para encontrar multiplicadores duais ótimos ou quase-
ótimos. Nesta seção apresentamos uma revisão dos métodos desenvolvidos para a
busca do melhor conjunto de multiplicadores nas relaxações Lagrangeana,
surrogate e combinadas Lagrangeana-surrogate. A literatura evidencia que o
método dos subgradientes está sendo utilizado com maior freqüência para
resolver os duais das relaxações Lagrangeana, surrogate ou Lagrangeana-
surrogate(Fumero, 2001, é uma referência recente para o método dos
subgradientes).
Os algoritmos utilizados para resolver o dual Lagrangeano são, basicamente, o
método dos subgradientes, variantes dos procedimentos de decomposição, sejam
eles de Benders (Schrijver, 1986) ou Dantzig-Wolfe (Minoux, 1986; Baker &
Sheasby, 1999; Wentges, 1997; Klose, 2000) e algoritmos especializados com base
no método de ajuste de multiplicadores (Erlenkotter, 1978; Fisher et al., 1980;
Galvão et al., 2000). Os métodos dos subgradientes e de ajuste de
multiplicadores abordam diretamente o problema (Du), enquanto os procedimentos
de decomposição de Benders e Dantzig-Wolfe resolvem reformulações de (Du); tais
reformulações podem ser encontradas, por exemplo, em Fisher (1981), Nemhauser
& Wolsey (1988) e Galvão (1993).
Diversos algoritmos foram propostos para resolver o dual surrogate. Os
trabalhos de Banerjee (1971) e Karwan & Rardin (1979, 1984) utilizam o
procedimento de Benders. Karwan & Rardin (1981) propõem utilizar um
algoritmo branch and bound. Glover (1975) desenvolveu um algoritmo que pode ser
utilizado para encontrar multiplicadores ótimos para problemas com duas
restrições. Dyer (1980) propôs dois algoritmos que são extensões naturais de
métodos utilizados na relaxação Lagrangeana. Gavish & Pirkul (1985)
propuseram um algoritmo para problemas com duas restrições e depois
incorporaram este algoritmo a uma heurística para calcular multiplicadores para
problemas com mais de duas restrições. Sarin et al. (1987) desenvolveram um
procedimento para a busca dos multiplicadores do dual surrogate utilizando uma
sucessão de buscas no dual Lagrangeano.
Outra estratégia utilizada é a seguinte: relaxar as condições de integralidade
das variáveis de decisão no problema surrogate e utilizar o método dos
subgradientes para resolver o dual surrogate. Esta estratégia foi proposta por
Lorena & Lopez (1994) para resolver o problema de recobrimento de conjuntos
e por Lorena & Narciso (1996) para resolver o problema de alocação
generalizado. Nesta mesma linha de pesquisa Galvão et al. (2000) compararam o
uso das relaxações Lagrangeana e surrogate para resolver o problema de
localização de máxima cobertura. Almiñana & Pastor (1997) adaptaram a
heurística de Lorena & Lopez (1994) para resolver o problema de cobertura
de conjuntos com custo unitário. Para resolver o problema (DLS[/img/fbpe/pope/
v22n3/a06img14.gif]), Lorena & Senne (1996) e Narciso & Lorena (1999)
utilizaram o método dos subgradientes.
Na literatura são relatadas algumas estratégias para resolver (D[/img/fbpe/
pope/v22n3/a06img15.gif]) . Glover (1975) sugere manter uw=0. Notando-se que
Glover utiliza o mesmo conjunto de restrições para as duas relaxações, isto
implica em relaxar um subconjunto destas restrições de forma Lagrangeana e seu
complemento de forma surrogate (Karwan & Rardin, 1980, provaram, com um
contra-exemplo, que esta estratégia pode impedir que seja encontrada a solução
ótima para a relaxação combinada Lagrangeana-surrogate). No mesmo trabalho
Glover (1975) sugere que fazendo u=w pode ser possível melhorar o limite obtido
com a relaxação Lagrangeana. Uma das heurísticas de Espejo et al. (2003) usa
esta estratégia para resolver o problema de localização hierárquica de máxima
cobertura. Karwan & Rardin (1980) propuseram a seguinte heurística para
resolver (D<formula/>): Resolver primeiro (Dw) e
encontrar o conjunto de multiplicadores surrogate ótimos, w*, tentando depois
melhorar o valor de v(Dw) resolvendo <formula/>. O
trabalho de Gavish & Pirkul (1985) apresenta duas implementações desta
heurística. A estratégia utilizada por John & Kochenberger (1988) foi fixar
o conjunto de multiplicadores surrogate, <formula/>, e
resolver o problema (D<formula/>) utilizando o método
dos subgradientes.
6. Relações Teóricas entre as Relaxações Lagrangeana, Surrogate e Combinada
Lagrangeana-surrogate
Nesta seção apresentamos os principais resultados teóricos que mostram as
relações entre os limites obtidos com as relaxações Lagrangeana, surrogate e
combinada Lagrangeana-surrogate. É importante observar que os resultados
apresentados nesta seção são válidos unicamente para problemas de minimização.
A seguinte notação adicional é utilizada para facilitar o entendimento dos
resultados: (DRLPu), dual da relaxação de programação linear do problema
Lagrangeano; (DRLPw), dual da relaxação de programação linear do problema
surrogate e (D<formula/>), dual do problema combinado
Lagrangeano-surrogate quando u=w.
Os resultados teóricos que seguem foram discutidos em Galvão et al. (2002) e
Espejo et al. (2003); um resumo deles é incluído aqui para complementar o
trabalho. Geoffrion (1974) provou que v(RLP) = v(DRLPu) £ v(Du). Ele provou
também que se (Pu) possui a propriedade de integralidade, então v(DRLPu) = v
(Du). Greenberg & Pierskalla (1970) provaram quev(RLP) £ v(Du) £ v(Dw) £ v
(P). Karwan & Rardin (1979) provaram que v(RLP) = v(DRLPu) = v(DRLPw) e
que, se (Pw)possui a propriedade de integralidade, então v(RLP) = v(Du) = v
(Dw) (Note que se Pw possui a propriedade de integralidade, então Pu também a
possui). No artigo de Karwan & Rardin (1980) é dada a seguinte relação: v
(Dw) £ v(D<formula/>) £ v(P). Finalmente,
Nieuwenhuizen (1999) provou que v(Du) £ v(D[/img/fbpe/pope/v22n3/
a06img20.gif]) £ v(Dw). Note que nesse último conjunto de desigualdades v(D(D[/
img/fbpe/pope/v22n3/a06img20.gif]) £ v(Dw) não significa que os vetores de
multiplicadores wsão os mesmos nos dois problemas duais; em v(D(D[/img/fbpe/
pope/v22n3/a06img20.gif]) no entanto os vetores usados nas relaxações
Lagrangeana e surrogatesão os mesmos.
Em resumo, para problemas de minimização podemos escrever-se as seguintes
relações:
v(RLP)£v(Du)£v(D<formula/>)£v(Dw)£v(D[/img/
fbpe/pope/v22n3/a06img15.gif])£v(P).
Para resolver um dado problema de programação inteira podem ser criadas várias
relaxações, dependendo da escolha das restrições a serem relaxadas. A escolha
das restrições a serem relaxadas pode afetar tanto o valor da solução ótima do
dual da relaxação quanto o esforço computacional requerido para avaliar e
atualizar a função dual durante o processo de solução do mesmo. Há portanto
dois fatores conflitantes que devem ser avaliados: a facilidade de solução do
problema dual (que depende da natureza do problema relaxado correspondente) e a
qualidade do limite gerado para o problema original. A possibilidade de se
gerar problemas que sejam mais fáceis de serem resolvidos, quando comparados ao
problema original, depende da estrutura do problema original e do grau de
separabilidade obtido através da relaxação das restrições escolhidas. De
maneira geral pode-se dizer que as relaxações que geram melhores limites
requerem maior tempo computacional, enquanto relaxações que produzem problemas
muito fáceis de serem resolvidos geram limites de pior qualidade.
Uma estratégia importante que tem sido utilizada para melhorar os limites
obtidos com o dual de uma relaxação é adicionar novas restrições que sejam
redundantes no problema (P). Quando algumas das restrições são relaxadas este
novo conjunto de restrições pode deixar de ser redundante. Isto deve ser feito
objetivando que o espaço de soluções viáveis do problema relaxado, com as novas
restrições, seja mais restrito que espaço de soluções da relaxação sem tais
restrições redundantes para (P).
7. Ilustração do Uso de uma Relaxação Combinada Lagrangeana-surrogate
Usaremos o Problema de Localização Hierárquico de Máxima Cobertura
(Hierarchical Covering Location Problem, HCLP) para mostrar o uso de uma
relaxação combinada L-S. Esta relaxação, desenvolvida e mostrada em maior
detalhe em Espejo (2001) e Espejo et al. (2003), é resumida aqui para fins
ilustrativos.
Os modelos de localização com restrições de cobertura pertencem à categoria de
modelos que provêm cobertura para áreas de demanda. Nestes modelos, comumente
usados em aplicações relacionadas à localização de facilidades de emergência,
uma área de demanda é considerada coberta se está dentro de uma distância
crítica pré-estabelecida de pelo menos uma das facilidades existentes. O HCLP,
definido por Moore & ReVelle (1982) para localizar serviços de saúde em
Honduras, é uma extensão hierárquica de dois níveis do Problema de Localização
de Máxima Cobertura (Maximal Covering Location Problem, MCLP).
Moore & ReVelle (1982) descreveram um sistema de localização hierárquica de
dois níveis da seguinte maneira: considere um sistema que fornece 2 níveis de
serviços e que possui 2 níveis de facilidades. Neste sistema um nível de
serviço s está disponível somente em uma facilidade de nível igual ou superior
a s. O problema a ser resolvido é então o de localizar um dado número de
facilidades para cada um dos dois níveis definidos, de maneira que se maximize
a população que tenha acesso aos dois níveis de serviço.
As distâncias críticas definidas por Moore & ReVelle (1982) são diferentes
para os dois níveis de serviço, e as distâncias críticas para o serviço de
nível 1 são diferentes para os dois tipos de facilidades. Seja R1 a distância
crítica para o serviço de nível 1 oferecido pela facilidade de nível 1 e seja
R2 a distância crítica para o serviço de nível 1 oferecido pela facilidade de
nível 2. Por outro lado, seja T1 a distância crítica para o serviço de nível 2.
Por hipótese as facilidades de nível superior são as mais atraentes; assume-se
portanto que R1<R2<T1. O modelo matemático correspondente pode ser escrito
como:
onde J = {1,2,...,m} é o conjunto de áreas de demanda, I = {1,2,...,n} é o
conjunto de locais onde as facilidades podem ser instaladas, fj é a população
da área de demanda j,aij = 1 se a área de demanda j puder ser coberta pelo
serviço de nível 1 (dentro da distância crítica R1), oferecido pela facilidade
de nível 1 localizada em iÎI (aij = 0 caso contrário), bij = 1 se a área de
demanda j puder ser coberta pelo serviço de nível 1 (dentro da distância
crítica R2), oferecido pela facilidade de nível 2 localizada em iÎI (bij = 0
caso contrário), cij = 1 se a área de demanda j puder ser coberta pelo serviço
de nível 2 (dentro da distância crítica T1), oferecido pela facilidade de nível
2 localizada em iÎI (cij = 0 caso contrário), p é o número de facilidades de
nível 1 a serem localizadas, q é o número de facilidades de nível 2 a serem
localizadas e xj, yi e zi são as variáveis de decisão. xj = 1 se a área de
demanda jÎJ é coberta (xj = 0 caso contrário); yi = 1 se uma facilidade de
nível 1 é localizada em iÎI (yi = 0 caso contrário); zi = 1 se uma facilidade
de nível 2 é localizada em iÎI (zi = 0 caso contrário).
No caso do HCLP uma restrição combinada Lagrangeana-surrogate pode ser obtida
da seguinte maneira. Considere dois vetores W1 = [w,s] ³ 0 e V1 = [l,m] ³ 0.
Uma restrição surrogate é formada combinando as restrições de cobertura (2) e
(3), obtendo-se:
Esta restrição pode ser adicionada à formulação original do HCLP (note-se que
ela é redundante em relação a esta formulação). Obtém-se:
sujeito a
e (2)-(7).
Dualizando as restrições (2) e (3) utilizando o vetor V1 = [l,m] ³ 0, obtemos:
sujeito a (3a) e (4)-(7).
Ou, fazendo
obtemos finalmente:
e (4)-(7). É importante notar que quando W1
¹
V1 HCLP<formula/> é um problema difícil de ser
resolvido: as variáveis yi ezique maximizam [/img/fbpe/pope/v22n3/
a06img25.gif]aiyi+<formula/>bizi na função objetivo
não são necessariamente as mesmas que maximizam[/img/fbpe/pope/v22n3/
a06img25.gif]a<formula/>yi+[/img/fbpe/pope/v22n3/
a06img25.gif]b<formula/>zi na restrição (3a).
Se fizermos W1=V1 (em cujo casowj=l j,sj=mj
"
j), então:
a restrição (3a) torna-se neste caso:
Desta vez yi ezi podem ser determinadas buscando-se maximizar[/img/fbpe/pope/
v22n3/a06img25.gif]aiyi+<formula/>bizitanto na função
objetivo como na restrição (3a). Uma vez que para maximizar xj deve-se buscar
maximizar tanto<formula/>aiyicomo[/img/fbpe/pope/
v22n3/a06img25.gif]bi
ziem (3a), e levando em conta que
zi =q, obtém-se:
onde C=åpai+åqbi. åpaié a soma dos p maiores-i (empates resolvidos
arbitrariamente),åqbié a soma dos q maiores-i (empates novamente resolvidos
arbitrariamente). <formula/> é portanto um problema da
mochila 0-1 com coeficientes fracionários.
É interessante notar que a relaxação (HCLP <formula/>)
é o caso mais geral das relaxações apresentadas em Espejo et al. (2003) para o
HCLP. Com efeito, fazendow=s=0 em (HCLP <formula/>)
obtemos imediatamente a relaxação Lagrangeana (HCLPlm). Por outro lado,
fazendol=m=0 em (HCLP <formula/>) obtemos a relaxação
surrogate (HCLPws). Finalmente, aplicando os resultados teóricos apresentados
na Seção 6 e notando que a relaxação Lagrangeana de HCLP possui a propriedade
da integralidade, é possível escrever:
v(RLHCLP) = v(DRLHCLPlm) = v(DRLHCLPlm) = v(DHCLPlm) ³ v(DHCLP[/img/fbpe/pope/
v22n3/a06img31.gif]) ³v(DHCLP--) ³ v(DHCLP[/img/fbpe/pope/v22n3/
a06img24.gif]) ³ v(HCLP).
Com a finalidade de ilustrar, para o HCLP, o desempenho da relaxação combinada
L-S em relação às relaxações Lagrangeana e surrogate, reproduzimos na tabela
abaixo os resultados obtidos em Espejo et al. (2003). Os problemas-teste
utilizados nessa tabela foram os seguintes: S55, rede definida por Swain
(1971); G&R100 e G&R150, que correspondem às redes geradas
aleatoriamente por Galvão & ReVelle (1996); B300, B500 e B700, obtidos da
biblioteca eletrônica de Beasley para o problema das p-medianas (problemas
Pmed11, Pmed21 e Pmed31). As heurísticas relaxadas (Heur_Surr Relaxada e
Heur_L-S Relaxada) correspondem à solução dos problemas da mochila
correspondentes relaxando as condições de integralidade.
Como pode ser observado na tabela acima, a média dos gaps obtidos para os
problemas teste não difere significativamente entre as diversas relaxações
utilizadas, para o mesmo conjunto de problemas. Poder-se-ia esperar, dados os
resultados teóricos apresentados, que os melhores limites poderiam ser obtidos
quando são solucionados os problemas da mochila 0-1 nas relaxações combinada
Lagrangeana-surrogate e surrogate do problema. Isto, porém, não foi geralmente
observado. Nossa experiência prática em resolver o problema da mochila com
coeficientes fracionários explica o porque destes resultados. Maiores detalhes
podem ser encontrados em Espejo et al. (2003).
8. Conclusões
Greenberg & Pierskalla (1970) propuseram combinar as relaxações Lagrangeana
e surrogate para diminuir o gap dual. Os autores indicaram a necessidade de um
desenvolvimento tanto teórico quanto empírico para avaliar se esta proposta é
prática no contexto geral de resolver um problema de programação inteira.
Vários autores publicaram resultados teóricos importantes nesta linha de
pesquisa; poucos, porém, publicaram resultados computacionais conclusivos em
relação a esta proposta. Entre os trabalhos com resultados computacionais
disponíveis podemos citar Espejo (2001) e Espejo et al. (2003).
