Métodos de geração de colunas para problemas de atribuição

Production

Edson Luiz França Senne²  Luiz Antonio Nogueira Lorena¹  Silvely Nogueira De Almeida Salomão¹ 

[1] ,UNESP

关键词: Otimização combinatória;    problemas de atribuição;    relaxação lagrangeana;    geração de colunas;    Combinatorial optimization;    assignment problems;    lagrangean;    column generation;   

DOI  :  10.1590/S0103-65132007000100005

来源: SciELO

【 摘 要 】

Este trabalho apresenta métodos de geração de colunas para dois importantes problemas de atribuição: o Problema Generalizado de Atribuição (PGA) e o Problema de Atribuição de Antenas a Comutadores (PAAC). O PGA é um dos mais representativos problemas de Otimização Combinatória e consiste em otimizar a atribuição de n tarefas a m agentes, de forma que cada tarefa seja atribuída a exatamente um agente e a capacidade de cada agente seja respeitada. O PAAC consiste em atribuir n antenas a m comutadores em uma rede de telefonia celular, de forma a minimizar os custos de cabeamento entre antenas e comutadores e os custos de transferência de chamadas entre comutadores. A abordagem tradicional de geração de colunas é comparada com as propostas neste trabalho, que utilizam a relaxação lagrangeana/surrogate. São apresentados testes computacionais que demonstram a efetividade dos algoritmos propostos.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License