Relaxação Lagrangeana – Teoria

Fevereiro 5, 2012

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 F representada por

z = \min \{c(x): x \in P\}

sendo P o conjunto de pontos que satisfazem as restrições dessa formulação, c(x) a função objetivo e z o valor da solução ótima. Dizemos que uma formulação F_R, dada por

z_R = \min \{f(x): x \in R\}

é uma relaxação se todo ponto de P está em R, ou seja P \subseteq R e se f(x) \le c(x) para x \in P.

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, z_R \le z. 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 m restrições e n variáveis:

z^* = \min cx

Sujeito a

\begin{array}{llcl} & A_1x & \le & b_1 \\ & A_2x & \le & b_2 \\ & x & \ge & 0 \\ & x & \in & Z^n \end{array}

Onde A_1x \le b_1 representa as desigualdades que queremos relaxar e A_2x \le b_2 as desigualdades que vamos manter. A relaxação lagrangeana é então dada por

z(u) = \min cx - u(b_1 - A_1x)

Sujeito a

\begin{array}{llcll} & A_2x & \le & b_2 & \\ & x & \ge & 0 & \\ & x & \in & Z^n & \\ & u & \ge & 0, & u \in R^m_1 \end{array}

Onde u é um vetor representando os multiplicadores lagrangeanos (um por cada desigualdade removida). Por exemplo, considere a desigualdade j que será removida:

\sum_{i = 1}^n a_{ij} x_i \le b_j

Ao remover (11), o seguinte fator é subtraído da função objetivo

(1) u_j (b_j - \sum_{i = 1}^n a_{ij} x_i)

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 u^* que minimize z(u).

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 C e a outra ao conjunto de fábricas/instalações F. Cada cliente i pode ser potencialmente atendido pela fábrica j, a custo um c_{i,j}. Além disso, paga-se um custo c_j por abrir a fábrica j, dado por y_j. O objetivo é atender todos os clientes com o menor custo.

Vamos apresentar uma formulação linear inteira para esse problema. Seja x_{i,j} uma variável binária que vale 1 sse o cliente i é atendido pela fábrica j e a variável y_j uma variável binária que vale 1 sse a fábrica j foi aberta. Temos a seguinte formulação:

z = \min \sum_{i \in C, j \in F} x_{ij} c_{ij} + \sum_{j \in F} y_j c_j

Sujeito a

\begin{array}{llcll} (2) & \sum_{j \in F} x_{ij} & \ge & 1 & \forall \, i \in C \\ (3) & x_{ij} & \le & y_j & \forall i \in C, \forall j \in F \\ & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C, \forall j \in F \end{array}

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:

z_1(u) = \min \sum_{i \in C, j \in F} x_{ij} c_{ij} +
\sum_{j \in F} y_j c_j - \sum_{i \in C} u_i (\sum_{j \in F} x_{ij} - 1)

Sujeito a

\begin{array}{llcll} & x_{ij} & \le & y_j & \forall i \in C, \forall j \in F \\ & u_i & \ge & 0 & \forall i \in C\\ & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C, \forall j \in F \end{array}

Com um pouco de álgebra, é possível “fatorar” o somatório da função objetivo:

z_1(u) = \min \sum_{j \in F} (\sum_{i \in C} (x_{ij} (c_{ij} - u_{i})) + c_j y_j)) + \sum_{i \in C} u_i

Como o termo \sum_{i \in C} u_i é 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 j:

\min \sum_{i \in C} (x_{ij} (c_{ij} - u_{i})) + c_j y_j

Sujeito a:

\begin{array}{llcll} & x_{ij} & \le & y_j & \forall i \in C\\ & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C \end{array}

Cada um desses problemas pode ser resolvido por inspeção. Seja c'_{ij} = c_{ij} - u_{i}. Vamos considerar duas possibilidades. Se fizermos y_j = 0, não atenderemos nenhum cliente, levando a uma solução de custo 0. Se y_j = 1, só compensa atender aos clientes com c'_{ij} < 0. Assim, o custo ótimo dessa formulação é:

\min\{0, c_j + \sum_{c'_{ij} < 0} c'_{ij} \}

A outra alternativa consiste em relaxar a desigualdade (3). Nesse caso, depois de alguma álgebra, teremos:

z_2(u) = \min \sum_{i \in C, j \in F} x_{ij} (c_{ij} - u_{ij}) + \sum_{j \in F} y_j (c_j + (\sum_{i \in C} u_{ij}))

Sujeito a:

\begin{array}{llcll} & \sum_{j \in F} x_{ij} & \ge & 1 & \forall \, i \in C \\ & u_{ij} & \ge & 0 & \forall i \in C, j \in F\\ & x_{i,j}, y_{j} & \in & \{0, 1\} & \forall i \in C, \forall j \in F \end{array}

Note que como não há restrições misturando x e y, podemos resolver o modelo para cada tipo de variável separadamente. No caso da variável y, como c_j \ge 0 e u \ge 0, não compensa abrir fábrica nenhuma. No caso de x, podemos resolver de maneira independente para cada x_i, por inspeção. Seja c'_{ij} = c_{ij} - u_{ij}. Se c'_{ij} > 0, podemos fazer x_{ij} = 1. Caso contrário x_{ij} = 0, exceto no caso em que c'_{ij} \ge 0 para todo j \in F. Nesse caso, devido à restrição (25), temos que fazer x_{ij^*} = 1, onde j^* = \mbox{argmin}_{j \in F} \{c'_{ij} \}.

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 z_1^* = \max \{ z_1(u) : u \ge 0 \} e z_2^* = \max \{ z_2(u) : u \ge 0 \}, queremos o limitante dual que mais se aproxima de z. 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.

Comentários Desativados em Relaxação Lagrangeana – Teoria | combinatória poliédrica, programação linear, programação linear inteira | Permalink
Publicado por kunigami

Hooligan

Novembro 12, 2010

Na final brasileira da maratona de programação de 2009, caiu um problema relacionado a futebol, chamado Hooligan, cujo enunciado pode ser acessado aqui.

Vou tentar resumi-lo. Temos um campeonato onde todos os times se enfrentam exatamente k vezes. Em um campeonato por pontos corridos, como o Brasileirão, temos k=2. Porém, diferentemente de um campeonato normal, vitória vale 2 pontos (e não 3), empate 1 e derrota 0. Imagine agora que estamos a certa altura do campeonato e algumas partidas já foram jogadas. A pergunta é: existe uma combinação dos resultados dos jogos restantes que fará com que o time para o qual estamos torcendo, seja não somente o campeão, mas que também tenha mais pontos que o segundo colocado?

Esse problema pode ser modelado como fluxo em redes e resolvido com um algoritmo de fluxo máximo. No dia da prova pensamos em modelá-lo dessa forma, mas não conseguimos chegar a um modelo correto.

Fluxo em redes

A primeira coisa a se fazer, é processar as partidas já realizadas, computando os pontos de cada time de acordo com a regra. Depois, observamos que, sem perda de generalidade, podemos fazer o nosso time predileto ganhar todas as partidas que lhe restam.

Seja o número total de pontos que nosso time tem após todas essas considerações. Observe que é a melhor pontuação que o nosso time pode obter. Porém, para que ele ganhe o campeonato, dependemos da pontuação dos outros times. Queremos uma combinação de jogos em que nenhum dos times restantes tenha mais do que pontos.

Se, mesmo antes de considerar os jogos não realizados, já houver time com ou mais pontos, não há o que fazer. Consideremos então que todos os times têm no máximo pontos. Seja o número de pontos do time i. Queremos que um time i ganhe no máximo pontos com as próximas partidas.

Vamos definir nosso grafo. Crie um nó para cada partida restante e um nó para cada time, além dos vértices fonte e destino, s e t, respectivamente. Para cada partida p, crie uma aresta (s, p) com capacidade 2, que representa o total de pontos que aquela partida vale. Além do mais, sejam u e v os times envolvidos na partida p. Crie uma aresta (p,u) e (p,v), ambas com capacidade 2. Finalmente, para cada time i, crie uma aresta (i, t) com capacidade .

Modelagem de uma partida entre os times u e v.

Afirmamos que existe uma combinação de resultados tal que nosso time de escolha fique em primeiro lugar isolado, se e somente se, o fluxo máximo na grafo definido acima for exatamente igual a 2*npr onde npr é o número de partidas restantes.

Prova: Observe que se o fluxo máximo for 2*npr, todas as arestas que saem de s estarão saturadas, ou seja, estará passando 2 unidades de fluxo. Temos duas arestas saindo de cada partida p. Sejam fu e fv a quantidade de fluxo nessas arestas respectivamente. Dadas as 2 unidades de fluxo chegando em p, as possíveis saídas (fu, fv) são (2, 0), (1, 1) ou (0, 2), sendo que cada uma dessas possibilidades representa um possível resultado de jogo. Já para cada time i, a quantidade de fluxo que chega no seu vértice correspondente a partir de uma dada partida p, é a quantidade de pontos que ganhou com aquela partida. Por conseguinte, a quantidade de fluxo que sai dele é o total de pontos conquistados. Note que, devido à capacidade da aresta, estamos limitando a quantidade de pontos que um dado time pode ganhar. Assim, se o fluxo é 2*npr, significa que conseguimos distribuir os pontos das partidas restantes entre os times, de forma que nenhum deles alcance nosso time predileto.

Além disso, dada uma combinação de resultados das partidas, é fácil construir um fluxo máximo de tamanho 2*npr.

Modelagem de um time.

Uma otimização para que o grafo não fique muito grande é: se existem k’ partidas restantes entre os times u e v, ao invés de criar k’ nós, criamos apenas um, mas multiplicamos as capacidades das arestas de entrada e saída por k’.

Observe que o sistema de pontuação foi modificado para que essa modelagem fosse possível. Se a vitória valesse 3, não conseguiríamos modelar as pontuações (3, 0), (1, 1) e (0, 3).

Algoritmo Guloso

Alguns maratonistas implementaram uma solução gulosa, que foi aceita no site nuevo portal.

A ideia é a seguinte. Computamos os pontos dos jogos já ocorridos e também assumimos que o time escolhido ganha o restante de seus jogos. Além disso, assumimos, a princípio, que todos os outros times empatam seus jogos.

O passo guloso é assim: Verificamos se o nosso time está na liderança isolada. Se sim, então temos uma combinação de resultados válida. Caso contrário, selecionamos o primeiro colocado x (ou algum que esteja dividindo a liderança com nosso time) e o time pior classificado y que tinha inicialmente um jogo não jogado com x. Desfazemos o empate entre x e y e fazemos x perder pra y. Reordenamos os times com essa nova pontuação e repetimos o passo. Se não houver tal y, declaramos que não existe nenhuma configuração de jogos que leve à situação desejada.

Pensei em um contra-exemplo que pode estragar essa estratégia se nenhum cuidado adicional for tomado. Considere 7 times, A, B, C, D, E, F e G, sendo que estamos torcendo pelo time A. Suponha que k=1, e já tiveram vários jogos de forma que só restam as partidas: (B,E), (B,F), (C,E) e (D,E) e que A, B, C, D têm 7 pontos, F e G têm 5 e E tem 4 (depois de considerados os empates dos jogos restantes).

Imagine que o algoritmo selecione B para perder de E (que é o pior classificado), ficando B com 6 pontos e E com 5. Agora suponha que ele selecione C, que necessariamente tem que perder para E (é a única partida que lhe resta). C tem 6 e E tem 6. O único time que está empatado com A é o D, que só pode perder para E, fazendo com que D tenha 6 e E tenha 7. Agora E passa a ficar empatado com A, mas como E não tem mais jogos, o algoritmo vai acusar que não há solução.

Tabelas de classificação ao longo da execução do algoritmo guloso.

Porém, se B perder para F ao invés de E e tanto C quanto D perderem para E, todos esses times ficam com 6 pontos e A ficará na liderança isolada.

Tabelas de classificação ao longo da estratégia ótima.

Uma pergunta é: o resultado que eu usei como contra-exemplo pode ser obtido com alguma combinação de jogos? Eu fiz na mão e aparentemente dá sim. Tive inclusive que adicionar o vértice G para a conta bater :P (note que ele não é usado no contra-exemplo).

Porém, essa é uma pergunta que pode ser respondida com uma modelagem por fluxo em rede e uma consequente redução ao problema do fluxo máximo, usando as ideias do modelo apresentado anteriormente.

Comentários Desativados em Hooligan | grafos, maratona, programação linear | Permalink
Publicado por kunigami

Dijkstra e o caminho máximo

Agosto 13, 2010

O problema do caminho mínimo é um dos problemas mais conhecidos da computação. Nesse post, vou comentar um pouco sobre o problema do caminho mínimo e também do caminho máximo, apresentando modelos de PLI para ambos. Para simplificar, vou considerar apenas as instâncias onde o grafo é direcionado e os pesos nas arestas são positivos.

O problema dos caminhos mínimos pode ser modelado como fluxo em redes. Mais especificamente, pode ser reduzido para o problema do fluxo de custo mínimo. Assim, existe naturalmente um algoritmo polinomial para resolvê-lo. Porém, da mesma forma que existem algoritmos combinatórios para o fluxo máximo e o fluxo de custo mínimo, o algoritmo de Dijkstra resolve o problema dos caminhos mínimos de maneira muito eficiente. O algoritmo foi desenvolvido por Edsger Dijkstra em 1956 tomando café em um bar. Disse o autor em uma entrevista que levou 20 minutos para desenvolver um dos algoritmos mais famosos do mundo da computação.

Claramente um algoritmo que resolva o problema dos caminhos mínimos através de programação linear não será capaz de bater a eficiência do algoritmo de Dijkstra. Mas, para fins de modelagem, vou apresentar o modelo PLI desse problema. A redução para o problema do fluxo máximo de custo mínimo é simples: basta fazer com que o fluxo máximo seja igual a 1. O modelo completo fica:

(1) Para cada nó v do grafo que não a fonte ou o sorvedouro,

(2) Para cada aresta (ij),

(3) Para cada aresta (ij),

(4)

Desta forma, temos que todo vale 0 ou 1. Devido à conservação do fluxo, as arestas com formam um caminho de s a t. Além do mais, o valor da função objetivo consiste em minimizar o custo das arestas desse caminho, justamente a definição do menor caminho.

Caminho de custo máximo

Um problema semelhante ao do caminho de menor custo é o problema do caminho de maior custo. Uma possível aplicação para esse problema é a técnica de planejamento CPM (Critical Path Method). O CPM consiste em construir um grafo direcionado com vértices correspondendo às atividades e arestas representando as dependências entre elas (ou seja, se existe uma aresta a->b, então b só pode ser executada depois que a terminar). A cada atividade está associado um custo, que é seu tempo de execução. Observe que aqui, o custo está associado a um vértice, e não a uma aresta. Isso pode ser resolvido através de uma modificação no grafo: para cada vértice v, substitua-o por vértice v’ e v’, com uma aresta v’-> v”com o custo igual ao do vértice. Para toda aresta (v,u), criamos a aresta (v”,u) e para toda aresta (u,v), criamos a aresta (u,v’) (veja a figura abaixo).

Split de um vértice para transformar custo do vértice em custo da aresta

Outra característica desse grafo é que ele é acíclico. Assim, é possível resolvê-lo em tempo polinimial através de programação dinâmica. Porém, para um grafo geral, o problema do caminho máximo é NP-completo.

Há uma característica que garante a integralidade (ou seja, que a solução do PL coincide com a do PLI) de modelos de programação linear, que é chamada de unimodularidade total. Se a matriz de coeficientes das restrições de um programa linear satisfizer certas condições, ela é dita totalmente unimodular. Isso implica que o problema que foi modelado com esse programa linear pode ser resolvido em tempo polinomial. Dois exemplos de matrizes que possuem essa estrutura são as matrizes de coeficientes dos PL’s do problema do fluxo máximo e do fluxo máximo de custo mínimo. Isso quer dizer que a matriz do PL do caminho de custo mínimo é unimodular. À primeira vista, isso parece implicar que o problema do caminho máximo pode ser resolvido em tempo polinomial, já que é só mudar a função objetivo de minimização pra maximização e, já que não modificamos a matriz de restrições, a unimodularidade total é mantida.

O problema é que não basta apenas modificar a função objetivo para que o PL resolva o problema do caminho de custo máximo. Se fizermos apenas isso, vão aparecer ciclos direcionados de custo positivo, disjuntos do caminho de s a t, já que queremos maximizar a função objetivo. Na figura abaixo, as arestas coloridas formam uma solução viável, já que ciclos (em vermelho) respeitam a conservação de fluxo. Supondo que a capacidade das arestas seja 1, o custo total da solução abaixo é 51; O maior caminho nesse grafo tem custo 33, que é maior do que o caminho encontrado em verde (ou seja, não basta jogar fora os ciclos encontrados). No problema do caminho mínimo eles não vão aparecer e por isso o modelo é válido.

Uma solução viável para o modelo com maximização

Assim, é preciso usar restrições que eliminem ciclos, o que faz com que a matriz de restrições deixe de ser totalmente unimodular. Para eliminá-los, definimos variáveis auxiliares, , associadas aos vértices. A seguinte restrição, elimina ciclos direcionados:

(5) Para cada aresta (i,j), seja M um número suficientemente grande

Se passa fluxo por uma aresta, a restrição fica,

O que implica que . Caso contrário, a desigualdade fica,

que é sempre satisfeita, tornando-a redundante.

Para ver que tal desigualdade elimina ciclos, considere um ciclo direcionado no grafo com os vértices na seguinte ordem (repeti o último vértice para explicitar que é um ciclo), corforme a figura seguinte.

Ciclo direcionado

Se houver fluxo passando por esse ciclo direcionado, a desigualdade (5) vai forçar que , ou seja , o que não pode acontecer. É fácil ver que tal desigualdade não impede a formação do caminho s-t. Basta ir atribuindo valores crescentes para u ao longo do caminho.

1 Comentário | grafos, programação linear, programação linear inteira | Permalink
Publicado por kunigami

Modelos de Programação Linear: Fluxo em Redes

Agosto 6, 2010

Muitos problemas de otimização combinatória podem ser modelados como problemas de fluxo em rede. Revisando um pouco, uma rede de fluxo é um grafo direcionado onde cada aresta tem uma capacidade e um fluxo associados. O fluxo na aresta não pode ultrapassar sua capacidade. Além disso, um fluxo deve satisfazer a restrição de conservação de fluxo, ou seja, a quantidade de fluxo que entra em um vértice é a mesma que sai, com exceção de um nó fonte (denotado por s), de onde só sai fluxo e um nó sorvedouro (denotado por t) de aonde só entra fluxo. Vamos apresentar um modelo que representa essas restrições. A cada aresta (ij), associamos uma variável representando o fluxo que passa por ela. Seja sua capacidade.

Rede com capacidades não-inteiras

 

(1) Para cada nó v do grafo que não a fonte ou o sorvedouro,

(2) Para cada aresta (ij),

(3) Para cada aresta (ij),

O lado esquerdo da igualdade (1) representa o somatório do fluxo de todas as arestas que entram em v e o lado direito o somatório do fluxo de todas as arestas que saem de v. Em outras palavras, é a restrição de conservação de fluxo. A desigualdade (2) é a restrição da capacidade do fluxo e (3) é para mostrar que o fluxo não pode ser negativo.

Analogia com dutos: capacidade e conservação de fluxo

Existe uma versão mais eficiente do algoritmo Simplex para resolver fluxos em rede (network simplex). Além disso, alguns dos problemas que podem ser modelados como fluxo em rede possuem algoritmos combinatórios (ou seja, algoritmos específicos para resolvê-los de maneira mais eficiente do que através de programação linear). A seguir vou apresentar dois exemplos para os quais foram desenvolvidos algoritmos combinatórios: o problema do fluxo máximo e o problema do fluxo máximo de custo mínimo.

Fluxo Máximo

Se adicionarmos uma função objetivo para maximizar a quantidade total de fluxo que sai da fonte (que por sinal é o mesmo que chega no sorvedouro), ou seja,

(4)

Temos o modelo linear do problema do fluxo máximo. O algoritmo mais simples para resolvê-lo é o ford-fulkerson, com complexidade , onde |f| é o valor do fluxo máximo (ou seja, esse algoritmo é pseudo-polinomial) e um dos mais eficientes é um baseado numa técnica chamada Push-relabel, com complexidade .

Fluxo Máximo de Custo Mínimo

Se além da capacidade, as arestas tiverem custo associado , podemos considerar a seguinte função objetivo:

(5)

Porém, se os custos forem positivos, obviamente a melhor solução seria não passar nenhum fluxo. Por isso, temos que fixar que o fluxo que passa pela rede tenha um valor fixo d,

(6)

Tal problema é chamado de fluxo de custo mínimo. No caso em que d é o maior valor de fluxo possível, temos o problema do fluxo máximo de custo mínimo. Para este problema existe o algoritmo por cancelamento de ciclos, com complexidade , onde U e C são respectivamente a capacidade máxima e o custo máximo de alguma aresta, sendo este portanto um algoritmo pseudo-polinomial. O mais eficiente algoritmo até hoje é de o duplo-escalanamento (escalonamento de custo e capacidade) que é , sendo assim fortemente polinomial [2].

Conclusão

Esses modelos em particular possuem a propriedade de que se as capacidades da rede forem inteiras, o fluxo máximo também será. Ou seja, mesmo que x possa assumir valores reais, na solução ótima ela será inteira. Desta forma, a solução ótima do PLI (x inteira) e do PL (x real) coincidem. Assim, esse é um típico caso em que um PLI pode ser resolvido em tempo polinomial.

Para uma referência mais abrangente, consulte o livro do Ahuja, Magnanti e Orlin [1].

Referências:

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications.
[2] Advanced Algorithms MIT – Minimum cost maximum flow, Minimum cost circulation, Cost/Capacity scaling

2 comentários | grafos, programação linear | Permalink
Publicado por kunigami

Restrições disjuntas

Julho 5, 2010

Como se sabe, as restrições de um PL devem ser satisfeitas simultaneamente pelas variáveis. Do ponto de vista lógico, isso representa um AND. Porém, existe um modo de modelar um OR, ou seja, permitir que as variáveis satisfaçam uma ou outra restrição? A resposta é sim, e essa modelagem é obtida através das restrições disjuntas.

Vamos começar por um exemplo de uma dimensão. Suponha que queiramos que x satisfaça x <= 1 ou x >= 3. Para isso, introduzimos uma novo variável y binária (ou seja y=0 ou y=1). Se x satisfizer x <= 1, então y=0, se x satisfizer x >= 3, então y=1. Seja M um número positivo muito grande. Modificamos as desigualdades na seguinte forma:


Para entender o funcionamento desse modelo, suponha que y=0. Então o modelo fica:


Como M é suficientemente grande, x >= 3 – M será satisfeito para qualquer x. Ou seja, a desigualdade torna-se redundante e podemos desconsiderá-la. Agora supomos que y=1. Temos então:


A interpretação é análoga. A ideia básica dessa técnica consiste em tornar uma das desigualdades redundantes.

Podemos generalizar essa ideia para que, dado um conjunto de desigualdades, apenas uma delas seja satisfeita. Se tivermos três restrições para duas variáveis, por exemplo:



Introduzimos as variáveis . Se a primeira desigualdade for satisfeita, queremos que (análogo para as outras desigualdades). Consideramos o seguinte modelo:

Observe que exatamente um dos ‘s tem 1 e o resto tem 0. Ele age como um Multiplexador. Quando , dá pra ver que a segunda e terceira desigualdades ficam redundantes, já que os outros termos são sempre positivos e só tendem a aumentar o lado direito da desigualdade. Entretanto, todos os termos envolvendo da primeira equação zeram, fazendo com que ela fique na forma original. Os outros casos são análogos.

Referências

[1] http://www.dcc.unicamp.br/~cid/cursos/MO420/Material-didatico/

Comentários Desativados em Restrições disjuntas | programação linear | Permalink
Publicado por kunigami

Modelos de Programação Linear – Problema da Dieta

Junho 10, 2010

Esse é o primero post da série de modelagem de programação linear e programação linear inteira. Pretendo abordar vários problemas de otimização combinatória e apresentar uma modelagem de programação linear. Sempre que possível, apresentarei modelagens alternativas e explicarei a diferença entre elas. Para quem não conhece o assunto, considere ler as referências [1,2]. Para um conteúdo mais avançado, considere a leitura também de [3].

O problema mais básico para se modelar como programação linear é o problema da dieta, que pode ser enunciado como segue:

Considere três tipos de alimentos a, b, c, cada um com diferentes proporções dos nutrientes i, j, k por unidade. Na nossa dieta, devemos consumir uma quantidade mínima de cada nutriente, denotado aqui por . Vamos denotar por a quandidade do nutriente i em uma unidade do alimento a, nomeando de forma semelhante as quantidades para as outras combinações de alimento e nutriente. Considere que a unidade de cada tipo de alimento tem um custo associado, . Queremos escolher uma combinação de alimentos de forma a minimizar o custo.

Antes de mais nada, precisamos definir as variáveis do modelo. No caso será a quandidade de cada alimento na combinação: . Temos o seguinte modelo

sujeito a:

(1)

(2)

(3)

(4)

A restrição (4) nos garante que só teremos quantidade não negativas de cada alimento na mistura final, o que é razoável.

De maneira geral, o problema da dieta para um conjunto de alimentos A e um conjunto de nutrientes N pode ser escrito como

sujeito a:

Referências
[1] Otimização Combinatória
[2] Programação Linear
[3] http://www.dcc.unicamp.br/~cid/cursos/MO420/Material-didatico/

2 comentários | programação linear | Permalink
Publicado por kunigami